시뮬레이션 된 단일 연결 테이블
선형 테이블 :
선형 테이블 (순차 테이블이라고도 함)은 가장 기본적이고 단순하며 가장 일반적으로 사용되는 데이터 구조입니다.
선형 테이블의 데이터 요소 간의 관계는 일대일 관계입니다. 즉, 첫 번째 및 마지막 데이터 요소를 제외하고 다른 데이터 요소는 끝에 연결됩니다.
선형 테이블의 논리적 구조는 간단하여 구현 및 작동이 쉽습니다.
실제 애플리케이션에서 선형 테이블은 스택, 큐 및 문자열과 같은 특수 선형 테이블 형태로 사용됩니다.
선형 구조의 기본 특성은 다음과 같습니다.
1. 컬렉션에는 고유 한 "첫 번째 요소"가 있어야합니다.
2. 컬렉션에는 고유 한 "마지막 요소"가 있어야합니다.
3. 마지막 요소를 제외하고는 고유 한 후속 자 (최신 항목)가 있습니다.
4. 첫 번째 요소를 제외하고는 독특한 프론트 드라이브 (전면 조각)가 있습니다.
링크 된 목록 : 링크 된 목록
링크 된 목록은 물리적 저장 장치의 비 연속 및 비 순차적 저장 구조입니다. 데이터 요소의 논리적 순서는 링크 된 목록의 포인터 링크 순서를 통해 구현 된 각 데이터 항목이 "링크 포인트"에 포함된다는 것입니다.
링크는 클래스의 객체 이며이 유형을 링크라고 할 수 있습니다. 링크 된 목록에는 유사한 링크가 많이 있으며 각 링크에는 다음 링크에 참조 된 필드가 포함되어 있습니다.
링크 된 목록 객체 자체는 첫 번째 링크 노드에 대한 참조를 가지고 있습니다. (먼저없는 경우 위치에 위치 할 수 없습니다)
링크 된 목록은 배열 (첨자 사용)과 같은 데이터 항목에 직접 액세스 할 수는 없지만, 데이터 간의 관계와 관련하여, 즉 링크 노드에서 참조 된 다음 링크에 액세스하고, 필요한 데이터에 액세스 할 때까지 다음 링크에 액세스하고 헤드에 필요한 데이터를 삽입하고 확인하는 시간 복잡성이 O (1)이기 때문에 명시된 포인트를 찾아야하기 때문입니다. 이러한 작업은 O (N)의 효율성으로 링크 된 목록에서 노드의 절반을 검색해야합니다.
단일 링크 목록 :
선형 테이블은 "노드 시퀀스"로 표시되며 선형 링크 목록 (단일 링크 목록)이라고합니다.
임의 주소가있는 스토리지 장치 세트를 사용하여 데이터 요소를 선형 테이블에 저장하는 체인 액세스 데이터 구조입니다. (이 메모리 셀 세트 세트
링크 노드의 구조 :
노드 값을 저장하는 데이터 필드 데이터; 다음에 노드 참조를 저장하는 포인터 필드 (체인 필드)
링크 된 목록은 각 노드의 링크 도메인을 통해 선형 테이블의 n 노드를 논리 순서로 연결합니다.
노드 당 링크 필드가 하나만있는 링크 된 목록을 단일 링크 목록이라고합니다. 한 방향으로, 후속 결절에 대한 언급 만 있습니다.
/*** 단일 링크 목록 : 헤더 삽입 방법 및 첫 번째 종료* 링크 된 목록의 왼쪽을 체인 헤드라고하며 오른쪽을 체인 테일이라고합니다. * 링크 된 목록의 오른쪽 끝을 고정하여 링크 된 목록의 오른쪽 끝을 보면 단일 링크 목록을 작성하는 헤더 삽입 메소드가 얻어지며 링크 된 목록은 왼쪽으로 계속 확장됩니다. * 헤더 삽입 방법에서 나오는 첫 번째 것은 꼬리 노드 * @author stone */ public class singlelinkedlist <t> {private link <t>입니다. // 첫 번째 노드 public singlelinkedList () {} public boolean isempty () {return first == null; } public void insertfirst (t data) {// 체인 링크의 헤드에 삽입 <t> newlink = new Link <t> (data); newlink.next = 첫 번째; // 새 노드의 다음은 이전 노드를 가리 킵니다. First = Newlink; } public link <t> deletefirst () {// 체인 헤더 링크 <t> temp = first; 첫 번째 = first.next; // 첫 번째 노드를 임시로 변경합니다. } public link <t> find (t t) {link <t> find = first; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} 찾기 찾기; } public link <t> delete (t t) {if (isempty ()) {return null; } else {if (first.data.equals (t)) {link <t> temp = first; 첫 번째 = first.next; // 첫 번째 노드를 다음 노드로 변경합니다. }} link <t> p = 먼저; 링크 <t> q = 첫 번째; while (! p.data.equals (t)) {if (p.next == null) {// 체인 끝에 가입하지만 찾을 수없는 return null; } else {q = p; p = p.next; }} q.next = p.next; 반환 p; } public void displayList () {// transip system.out.println ( "list (첫 번째-> last) :"); 링크 <t> current = 첫 번째; while (current! = null) {current.displayLink (); current = current.next; }} public void displayListReverse () {// 횡선 트래버스 링크 <t> p = first, q = first.next, t; (q! = null) {// 포인터가 반전되면, 트래버스 데이터 순서는 후진 t = q.next; // no3 if (p == first) {// 원래 헤더 일 때 헤드의 .next는 비어 있어야합니다. p.next = null; } q.next = p; // no3-> no1 포인터 리버스 p = q; // start는 리버스 q = t입니다. // no3 start} // 위의 루프의 if에서 first.next는 비어 있고 Q가 null이고 루프를 실행하지 않을 때 p는 가장 원래의 데이터 항목입니다. 반전 후, P는 첫 번째 = P에 할당된다; displayList (); } 클래스 링크 <t> {// 링크 지점 t 데이터; // 데이터 필드 링크 <T> 다음; // 후속 포인터, 노드 체인 도메인 링크 (t data) {this.data = data; } void displayLink () {System.out.println ( "데이터는" + data.toString ()); }} public static void main (String [] args) {SinglElinkedList <integer> list = new SinglelinkedList <integer> (); list.insertfirst (33); list.insertfirst (78); list.insertfirst (24); list.insertfirst (22); list.insertfirst (56); list.displayList (); list.deletefirst (); list.displayList (); System.out.println ( "찾기 :" + list.find (56)); System.out.println ( "찾기 :" + list.find (33)); System.out.println ( "삭제 찾기 :" + list.delete (99)); System.out.println ( "삭제 찾기 :" + list.delete (24)); list.displayList (); System.out.println ( "--- 리버스 ----"); list.displaylistrevesse (); }}인쇄
List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete 찾기 : linked_list.singlelinkedlist$link@17dfafd1 목록 (첫 번째-> 마지막) : 데이터는 22입니다. 데이터는 78입니다. 데이터는 78입니다. 데이터는 33 --- 리버스 --- 목록 (첫 번째-> 마지막) : 데이터는 78입니다. 데이터는 22입니다.
단일 링크 목록 : 꼬리 삽입 방법, 먼저 링크 된 목록의 왼쪽 끝이 고정되면 링크 된 목록이 오른쪽으로 계속 확장되며 링크 된 목록을 설정하는이 방법을 꼬리 삽입 방법이라고합니다.
테일 삽입 방법으로 링크 된 목록을 만들 때 헤드 포인터가 고정되어 있으므로 링크 된 목록의 오른쪽으로 확장하기 위해 테일 포인터를 설정해야합니다.
테일 삽입 방법에서 가장 먼저 나오는 것은 헤드 노드입니다.
공개 클래스 SinglElinkedList2 <t> {Private Link <t> 헤드; // 첫 번째 노드 public singlelinkedList2 () {} public boolean isempty () {return head == null; } public void insertLast (t data) {// insert link <t> newlink = new Link <t> (data); if (head! = null) {link <t> nextp = head.next; if (nextp == null) {head.next = newlink; } else {link <t> rear = null; while (nextp! = null) {rear = nextp; nextp = nextp.next; } rear.next = newlink; }} else {head = newlink; }} public link <t> deletelast () {// 체인 링크의 꼬리를 삭제 <t> p = head; 링크 <t> q = 헤드; (p.next! = null) {// p의 다음 노드는 비어 있지 않으며 q는 현재 p와 같다 (즉, q는 이전의 P와 같고 p는 다음과 같다). 루프가 끝나면 q는 체인 q = p의 두 번째 끝과 동일합니다. p = p.next; } // q.next = null 삭제; 반환 p; } public link <t> find (t t) {link <t> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} 찾기 찾기; } public link <t> delete (t t) {if (isempty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; head = head.next; // 첫 번째 노드를 임시로 변경합니다. }} link <t> p = 헤드; 링크 <t> q = 헤드; while (! p.data.equals (t)) {if (p.next == null) {// return null이 체인 끝에서 발견되지 않았 음을 의미합니다. } else {q = p; p = p.next; }} q.next = p.next; 반환 p; } public void displayList () {// Travel System.out.println ( "list (head-> last) :"); 링크 <t> current = 헤드; while (current! = null) {current.displayLink (); current = current.next; }} public void displayListReverse () {// 횡선 트래버스 링크 <t> p = head, q = head.next, t; while (q! = null) {// 포인터가 반전되고 트래버스 데이터 순서가 뒤로 이동합니다. t = q.next; // no3 if (p == head) {// 원래 헤더 일 때 헤드의 .next는 비어 있어야합니다. p.next = null; } q.next = p; // no3-> no1 포인터 리버스 p = q; // start는 리버스 q = t입니다. // no3 start} // 위의 루프의 if에서 head.next는 Q가 비어 있고 Q가 널이고 루프를 실행하지 않을 때 P는 가장 원래의 데이터 항목입니다. 역전 후, P는 헤드 헤드 = P에 할당된다; displayList (); } 클래스 링크 <t> {// 링크 지점 t 데이터; // 데이터 도메인 링크 <T> 다음; // 연속 포인터, 노드 체인 도메인 링크 (t data) {this.data = data; } void displayLink () {System.out.println ( "데이터는" + data.toString ()); }} public static void main (string [] args) {singlelinkedList2 <integer> list = new SinglElinkedList2 <integer> (); list.insertlast (33); list.insertlast (78); list.insertlast (24); list.insertlast (22); list.insertlast (56); list.displayList (); list.deletelast (); list.displayList (); System.out.println ( "찾기 :" + list.find (56)); System.out.println ( "찾기 :" + list.find (33)); System.out.println ( "삭제 찾기 :" + list.delete (99)); System.out.println ( "삭제 찾기 :" + list.delete (78)); list.displayList (); System.out.println ( "---- 리버스 -----"); list.displaylistrevesse (); }}인쇄
데이터는 33입니다. 데이터는 78입니다. 데이터는 24입니다. 데이터는 22입니다. 데이터는 56 목록 (Head-> Last) : 데이터는 33입니다. 데이터는 78입니다. 데이터는 24입니다. 데이터는 22입니다. null 찾기 : linked_list.singlinked_list.singlinked_list2$link@4b71bbc9 삭제 : Null Delete finde 삭제 : Null Delete finde. 찾기 : linked_list.singlelinkedlist2$link@17dfafd1 목록 (Head-> Last) : 데이터는 33입니다. 데이터는 24입니다. 데이터는 22 --- 역 (Head-> Last) : 데이터는 24입니다. 데이터는 33입니다.
링크 된 목록으로 스택 및 큐를 구현하기 위해 이중 엔드 링크 목록 시뮬레이션
더블 엔드 링크 목록 :
이중 엔드 링크 목록은 기존 링크 된 목록과 매우 유사합니다. 새로운 속성 만 추가되었습니다. 즉, 마지막 링크에 대한 참조는 후면입니다.
이런 식으로, 체인 끝에 삽입하는 것은 매우 쉬워 질 것입니다. 마지막 노드를 검색하기 위해 루핑없이 새로 추가 된 노드로 후면의 다음을 변경하면 insertfirst 및 insertLast가 있습니다.
체인 헤더를 삭제할 때는 기준점 만 변경하면됩니다. 체인 테일을 삭제할 때는 두 번째 노드의 다음 노드를 비워야합니다.
참조 지점이 없으므로 작업을 읽으려면 루프가 필요합니다.
/ *** 이중 엔드 링크 목록* @Author Stone*/ Public Class TwoendpointList <t> {private link <t> head; // 첫 번째 노드 개인 링크 <t> 후면; // tail pointer public public twoendpointList () {} public t peekhead () {if (head! = null) {return head.data; } return null; } public boolean isempty () {return head == null; } public void insertfirst (t data) {// 체인 링크의 헤드에 삽입 <t> newlink = new Link <t> (data); newlink.next = 헤드; // 새 노드의 다음은 이전 노드 헤드 = NewLink를 가리 킵니다. } public void insertLast (t data) {// insert link <t> newlink = new Link <t> (data); if (head == null) {rear = null; } if (rear! = null) {rear.next = newlink; } else {head = newlink; head.next = 후면; } rear = newlink; // 다음에 삽입 할 때 후면에서 삽입} public t deletehead () {// 체인 헤더를 삭제하면 (isempty ()) return null; 링크 <t> temp = 헤드; head = head.next; // 첫 번째 노드를 다음 노드로 변경하면 (head == null) {<span style = "화이트 공간 : pre"> </span> rear = head; } return temp.data; } public t find (t t) {if (isempty ()) {return null; } link <t> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} if (find == null) {return null; } return find.data; } public t delete (t t) {if (isempty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; head = head.next; // 첫 번째 노드를 다음 노드로 변경하십시오. }} link <t> p = 헤드; 링크 <t> q = 헤드; while (! p.data.equals (t)) {if (p.next == NULL) {// 류가 체인 끝에서 return null이 발견되지 않았 음을 나타냅니다. } else {q = p; p = p.next; }} q.next = p.next; 반환 p.data; } public void displayList () {// Travel System.out.println ( "list (head-> last) :"); 링크 <t> current = 헤드; while (current! = null) {current.displayLink (); current = current.next; }} public void displayListReverse () {// vereverse traversal if (isempty ()) {return; } link <t> p = head, q = head.next, t; while (q! = null) {// 포인터가 반전되고 트래버스 데이터 순서가 뒤로 이동합니다. t = q.next; // no3 if (p == head) {// 원래 헤드 일 때 머리의 .next는 비어 있어야합니다. p.next = null; } q.next = p; // no3-> no1 포인터 리버스 p = q; // start는 리버스 q = t입니다. // no3 start} // 위의 루프의 if에서 head.next는 비어 있고 Q가 null이고 루프를 실행하지 않을 때 p는 가장 원래의 데이터 항목입니다. 역전 후, P는 헤드 헤드 = P에 할당된다; displayList (); } class link <t> {// 링크 노드 t 데이터; // 데이터 도메인 링크 <T> 다음; // 연속 포인터, 노드 체인 도메인 링크 (t data) {this.data = data; } void displayLink () {System.out.println ( "데이터는" + data.toString ()); }} public static void main (String [] args) {TwoendpointList <integer> list = new TwoendpointList <integer> (); list.insertlast (1); list.insertfirst (2); list.insertlast (3); list.insertfirst (4); list.insertlast (5); list.displayList (); list.deletehead (); list.displayList (); System.out.println ( "찾기 :" + list.find (6)); System.out.println ( "찾기 :" + list.find (3)); System.out.println ( "삭제 찾기 :" + list.delete (6)); System.out.println ( "삭제 찾기 :" + list.delete (5)); list.displayList (); System.out.println ( "--- 리버스 ----"); list.displaylistrevesse (); }}인쇄
데이터는 4입니다. 데이터는 2입니다. 데이터는 1입니다. 데이터는 3입니다. 데이터는 5 목록 (Head-> Last) : 데이터는 2입니다. 데이터는 3입니다. 데이터는 3입니다. 데이터는 5입니다. null 찾기 : 3 삭제 찾기 : 5 목록 (Head) : 데이터는 3입니다. 데이터는 3입니다. 데이터는 2입니다. 데이터는 2입니다. 데이터는 3입니다.
링크 된 목록을 사용하여 스택을 구현하고 삽입하기 전에 단일 링크 목록을 사용하십시오.
이 클래스는 이중 엔드 링크 목록을 사용하여 구현합니다.
공개 클래스 LinkStack <t> {Private TwoendpointList <T> Datas; public linkstack () {datas = new TwoendpointList <t> (); } // 스택에 넣습니다. 공개 void push (t data) {datas.insertfirst (data); } // stack public t pop () {return datas.deletehead (); } // 스택의 상단을 확인 public t peek () {return datas.peekhead (); } // 스택이 빈 공개 부울 isempty () {return datas.isempty (); } public static void main (String [] args) {Linkstack <integer> stack = new Linkstack <integer> (); for (int i = 0; i <5; i ++) {stack.push (i); } for (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ( "Peek :" + Peek); } for (int i = 0; i <6; i ++) {integer pop = stack.pop (); System.out.println ( "팝 :" + 팝); } system.out.println ( "----"); for (int i = 5; i> 0; i-) {stack.push (i); } for (int i = 5; i> 0; i-) {integer peek = stack.peek (); System.out.println ( "Peek :" + Peek); } for (int i = 5; i> 0; i-) {integer pop = stack.pop (); System.out.println ( "팝 :" + 팝); }}}인쇄
엿보기 : 4 엿보기 : 4 엿보기 : 4 엿보기 : 4 엿보기 : 4 엿보기 : 4 팝 : 4 팝 : 4 팝 : 3 팝 : 2 팝 : 1 팝 : 1 팝 : 0 팝 : 0 팝 : 1 엿보기 : 1 팝 : 1 팝 : 1 팝 : 2 팝 : 4 팝 : 5
링크 된 목록 구현 큐는 이중 엔드 링크 목록을 사용하여 구현됩니다.
공개 클래스 Linkqueue <t> {private twoendpointList <T> 목록; public linkqueue () {list = new TwoendpointList <t> (); } // 대기열의 꼬리를 삽입 공개 void insert (t data) {list.insertlast (data); } // 팀의 헤드를 제거하여 public t remove () {return list.deletehead (); } // 팀의 헤드보기 public t peek () {return list.peekhead (); } public boolean isempty () {return list.isempty (); } public static void main (String [] args) {Linkqueue <integer> queue = new Linkqueue <integer> (); for (int i = 1; i <5; i ++) {queue.insert (i); } for (int i = 1; i <5; i ++) {integer peek = queue.peek (); System.out.println ( "Peek :" + Peek); } for (int i = 1; i <5; i ++) {integer remove = queue.remove (); System.out.println ( "제거 :" + 제거); } system.out.println ( "----"); for (int i = 5; i> 0; i-) {queue.insert (i); } for (int i = 5; i> 0; i-) {integer peek = queue.peek (); System.out.println ( "Peek2 :" + Peek); } for (int i = 5; i> 0; i-) {integer remove = queue.remove (); System.out.println ( "제거 :" + 제거); }}}인쇄
PEEK : 1 엿보기 : 1 엿보기 : 1 엿보기 : 1 엿보기 : 1 제거 : 1 제거 : 1 제거 : 2 제거 : 3 제거 : 4-5 Peek2 : 5 Peek2 : 5 Peek2 : 5 제거 : 4 제거 : 2 제거 : 2 제거 : 1 제거 : 1 제거 : 1 제거 :