연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조
q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2
q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입 삭제연산이많이발생하는경우에성능상의문제발생 순차자료구조는배열을이용하여구현하기때문에배열이갖고있는메모리사용의비효율성문제를그대로가짐 순차자료구조에서의연산시간에대한문제와저장공간에대한문제를개선한자료표현방법필요 3
q 연결자료구조 v 연결자료구조 (Linked Data Structure) 자료의논리적인순서와물리적인순서가일치하지않는자료구조 각원소에저장되어있는다음원소의주소에의해순서가연결되는방식 Ø 물리적인순서를맞추기위한오버헤드가발생하지않는다. 여러개의작은공간을연결하여하나의전체자료구조를표현 Ø 크기변경이유연하고더효율적으로메모리사용 연결리스트 리스트를연결자료구조로표현한구조 연결하는방식에따라단순연결리스트와원형연결리스트, 이중연결리스트, 이중원형연결리스트 4
q 연결자료구조 v 노드 연결자료구조에서하나의원소를표현하기위한단위구조 < 원소, 주소 > 의구조 데이터필드 (data field) Ø 원소의값을저장 Ø 저장할원소의형태에따라서하나이상의필드로구성 링크필드 (link field) Ø 다음노드의주소를저장 Ø 포인터변수를사용하여주소값을저장 5
q 연결자료구조 노드연결방법에대한이해 - 기차놀이 1 이름표뽑기 2 자기가뽑은이름의사람을찾아서연결하기 : 희진 삼식 삼순 Ø X 표를뽑은사람은마지막기차 기차는이름표를들고있는방향으로움직인다. 6
q 연결자료구조 노드연결방법에대한이해 - 기차놀이 기차놀이와연결리스트 Ø 기차놀이하는아이들 : 연결리스트의노드 Ø 이름표 : 노드의링크필드 선형리스트와연결리스트의비교 리스트 week=( 월, 화, 수, 목, 금, 토, 일 ) week 에대한선형리스트 7
q 연결자료구조 리스트 week=( 월, 화, 수, 목, 금, 토, 일 ) week 에대한연결리스트 8
q 연결자료구조 리스트이름 week - 연결리스트의시작을가리키는포인터변수 Ø 포인터변수 week 는연결리스트의첫번째노드를가리키는동시에연결된 리스트전체를의미 연결리스트의마지막노드의링크필드 - 노드의끝을표시하기위해서 null( 널 ) 저장 공백연결리스트 - 포인터변수 week에 null을저장 ( 널포인터 ) 각노드의필드에저장한값은포인터의점연산자를사용하여액세스 Ø week.data : 포인터 week가가리키는노드의데이터필드값 월 Ø week.link : 포인터 week가가리키는노드의링크필드에저장된주소값 리스트 week 의노드에대한 C 프로그램구조체정의 typedef struct Node{ char data[4]; struct Node* link; }; 9
q 연결자료구조 리스트이름 week - 연결리스트의시작을가리키는포인터변수 Ø 포인터변수 week 는연결리스트의첫번째노드를가리키는동시에연결된 리스트전체를의미 연결리스트의마지막노드의링크필드 - 노드의끝을표시하기위해서 null( 널 ) 저장 공백연결리스트 - 포인터변수 week에 null을저장 ( 널포인터 ) 각노드의필드에저장한값은포인터의점연산자를사용하여액세스 Ø week.data : 포인터 week가가리키는노드의데이터필드값 월 Ø week.link : 포인터 week가가리키는노드의링크필드에저장된주소값 리스트 week 의노드에대한 C 프로그램구조체정의 typedef struct Node{ char data[4]; struct Node* link; }; 10
q 단순연결리스트 v 단순연결리스트 (singly linked list) 노드가하나의링크필드에의해서다음노드와연결되는구조를가진연결리스트 연결리스트, 선형연결리스트 (linear linked list), 단순연결선형리스트 (singly linked linear list) 예 ) 11
q 단순연결리스트 v 단순연결리스트의삽입 리스트 week2=( 월, 금, 일 ) 에서원소 월 과 금 사이에새원소 수 삽입하기 1 삽입할새노드를만들공백노드를메모리에서가져와서포인터변수 new 가가리키게한다. 2 new 의데이터필드에 수 를저장한다. 12
q 단순연결리스트 3 new 의앞노드, 즉 월 노드의링크필드값을 new 의링크필드에저장 week2 100번지 200번지 300번지 100 월 200 금 300 일 null new 150 150 번지 수 200 4 월 노드의링크필드에 new 의값 (new 가가리키고있는새노드의주소 ) 을저장 100번지 200번지 300번지 week2 100 월 150 금 300 일 null 150 번지 new 150 수 200 13
q 단순연결리스트 v 단순연결리스트의삭제 리스트 week2=( 월, 수, 금, 일 ) 에서원소 수 삭제하기 1 삭제할원소의앞노드 ( 선행자 ) 를찾는다. 2 앞노드의링크필드에, 삭제할원소 수 의링크필드값을저장한다. 100번지 200번지 300번지 week2 100 월 200 150 번지 금 300 일 null 수 200 14
q 단순연결리스트 v 자유공간리스트 (free space list) 사용하기전의메모리나사용이끝난메모리를관리하기위해노드 로구성하여연결한리스트 자유공간리스트에서대기중인노드들 사용중인노드들 15
q 단순연결리스트 자유공간리스트에서의노드할당알고리즘 getnode( ) if (Free = null) then underflow( ); // 언더플로우처리루틴 new Free; // ❶ Free Free.link; // ❷ return new; end getnode( ) [ 알고리즘 6-1] 16
q 단순연결리스트 자유공간리스트에서의노드할당과정 자유공간리스트 free 에서노드를할당할때는항상첫번째노드할당 초기상태 1 new Free; 리스트 free 의첫번째노드의주소를포인터 new 에저장하여포인터 new 가할당할 노드를가리키게한다. Free 100 100 번지 200 200 번지 300 300 번지 400... null new 100 17
q 단순연결리스트 2 Free Free.link; 포인터 free 에리스트의두번째노드의주소 (Free.link) 저장 Free 200 100 번지 200번지 300번지 200 300 400 null... new 100 이제자유공간리스트 free 의첫번째노드는리스트에서의미적으로분리된 상태이므로포인터 new 를반환 (return new;) 해줌으로써새노드를할당 18
q 단순연결리스트 자유공간리스트로의노드반환알고리즘 returnnode(old) old.link Free; // ❶ Free old; // ❷ end returnnode( ) [ 알고리즘 6-2] 자유공간리스트로의노드반환과정 반환되는노드는자유공간리스트 free 의첫번째노드로다시삽입 초기상태 19
q 단순연결리스트 1 old.link Free; 자유공간리스트 free 의첫번째노드주소를반환할노드포인터 old.link 에저장 하여포인터 old 의노드가리스트 free 의첫번째노드를가리키게한다. Free 200 200 번지 300 300 번지 400... null old 100 100 번지 200 2 Free old; 포인터 old 의값즉, 반환할노드의주소를포인터 free 에저장하여리스트 free 의첫번째노드로지정 Free 100 200 번지 300 300 번지 400... old 100 100 번지 200 20
q 단순연결리스트 v 단순연결리스트의삽입알고리즘 첫번째노드로삽입하기 returnnode(old) old.link Free; // ❶ Free old; // ❷ end returnnode( ) [ 알고리즘 6-3] 1 new getnode( ); 삽입할노드를자유공간리스트에서할당받는다. 21
q 단순연결리스트 2 new.data x; 새노드의데이터필드에 x 를저장 3 new.link L; 삽입할노드를연결하기위해서리스트의첫번째노드주소를삽입할새노드 new의링크필드에저장하여, 새노드 new가리스트의첫번째노드를가리키게한다. L 100 100 번지 200 200 번지 300 300 번지 null new 700 700 번지 x 100 22
q 단순연결리스트 4 L new; 리스트의첫번째노드주소를저장하고있는포인터 L 에, 새노드의주소를저장 하여, 포인터 L 이새노드를첫번째노드로가리키도록지정 L 700 100 번지 200 200 번지 300 300 번지 null new 700 700 번지 x 100 23
q 단순연결리스트 중간노드로삽입하기 리스트 L에서포인터변수 pre가가리키고있는노드의다음에데이터필드값이 x인새노드를삽입하는알고리즘 리스트의중간노드삽입알고리즘 insertmiddlenode(l, pre, x) new getnode( ); new.data x; if (L=null) then { // ❶ L new; // ❶-a new.link null; // ❶-b } else { // ❷ new.link pre.link; // ❷-a pre.link new; // ❷-b } end insertmiddlenode( ) [ 알고리즘 6-4] 24
q 단순연결리스트 Ø 리스트 L 이공백리스트인경우 1 L new; 리스트포인터 L 에새노드 new 의주소를저장하여, 새노드 new 가리스트의첫번째노드가되게한다. L new 700 700 700 번지 x 2 new.link null; 리스트의마지막노드 new 의링크필드에 null 을저장하여마지막노드임을표시 L 700 new 700 700 번지 x null 25
q 단순연결리스트 Ø 리스트 L 이공백리스트가아닌경우 1 new.link pre.link; 노드 pre 의링크필드값을노드 new 의링크필드에저장하여, 새노드 new 가노드 pre 의다음노드를가리키도록한다. L 100 100번지 200번지 200 300 300 번지 null pre 100 new 700 700 번지 x 200 26
q 단순연결리스트 2 pre.link new; 포인터 new 의값을노드 pre 의링크필드에저장하여, 노드 pre 가새노드 new 를 다음노드로가리키도록한다. L 100 100번지 200번지 700 300 300 번지 null pre 100 new 700 700 번지 x 200 27
q 단순연결리스트 마지막노드로삽입하기 새노드 new 를마지막노드로삽입하는알고리즘 insertlastnode(l, x) new getnode(); new.data x; new.link null; if (L = null) then { L new; return; } temp L; while (temp.link null) do temp temp.link; temp.link new; end insertlastnode() // ❶-a // ❶-b // ❷-a // ❷-b // ❷-c [ 알고리즘 6-5] 28
q 단순연결리스트 Ø 리스트 L 이공백리스트인경우 Ø [ 알고리즘 6-4] 에서공백리스트에노드를삽입하는연산과같은연산 Ø 삽입하는새노드 new 는리스트 L 의첫번째노드이자마지막노드 29
q 단순연결리스트 Ø 리스트 L 이공백리스트인경우 1 temp L; 현재리스트 L 의마지막노드를찾기위해노드를순회할임시포인터 temp 에리스트의첫번째노드의주소를지정 L 100 100 번지 200 200 번지 300 300 번지 null temp 100 2 while (temp.link null) do temp temp.link; while 반복문을수행하여순회포인터 temp가노드의링크필드를따라이동하면서링크필드가 null인마지막노드찾기수행 100번지 200번지 300번지 100 L 200 300 null temp 100 temp 200 temp 300 30
q 단순연결리스트 3 temp.link new; 순회포인터 temp 가가리키는노드즉, 리스트의마지막노드의링크필드에삽입 할새노드 new 의주소를저장하여, 리스트의마지막노드가새노드 new 를연결 L 100 100 번지 200 200 번지 300 300 번지 700 temp 300 700번지 new 700 x null 31
q 단순연결리스트 v 단순연결리스트의삭제알고리즘 리스트 L에서포인터 pre가가리키는노드의다음노드를삭제하는알고리즘 포인터 old : 삭제할노드 deletenode(l, pre) if (L = null) then error; else { old pre.link; if (old = null) then return; pre.link old.link; } returnnode(old); end deletenode( ) // ❶ // ❷ // ❷-a // ❸ // ❷-b // ❷-c [ 알고리즘 6-6] 32
q 단순연결리스트 Ø 리스트 L 이공백리스트가아닌경우 1 old pre.link; 노드 pre 의다음노드의주소를포인터 old 에저장하여, 포인터 old 가다음노드를가리키게한다. L 100 100 번지 200 200 번지 300 300 번지 400 400 번지 null pre 200 old 300 33
q 단순연결리스트 2 if (old = null) then return; 만약노드 pre 가리스트의마지막노드였다면 : Ø pre.link 의값은 null 이므로포인터 old 의값은 null 이된다. 결국노드 pre 다음의삭제할노드가없다는의미이므로삭제연산을수행하지못하고반환 (return). L 100 100 번지 200 200 번지 300 300 번지 null pre 300 old null 34
q 단순연결리스트 3 pre.link old.link; 삭제할노드 old 의다음노드 (old.link) 를노드 pre 의다음노드 (pre.link) 로연결 L 100 100 번지 200 200 번지 400 300 번지 400 400 번지 null pre 200 old 300 4 returnnode(old); 삭제한노드 old 를자유공간리스트에반환 35
q 단순연결리스트 v 단순연결리스트의노드탐색알고리즘 리스트의노드를처음부터하나씩순회하면서노드의데이터필드 의값과 x 를비교하여일치하는노드를찾는연산 searchnode(l, x) temp L; while (temp null) do { if (temp.data = x ) then return temp; temp temp.link; } return temp; end searchnode() // ❶ // ❷ // ❸ [ 알고리즘 6-7] 36
q 단순연결리스트 단순연결리스트프로그램 001 public class Ex6_1{ [ 예제 6-1] 002 public static void main(string args[]){ 003 LinkedList L = new LinkedList(); 004 System.out.println("(1) 공백리스트에노드 3개삽입하기 "); 005 L.insertLastNode(" 월 "); 006 L.insertLastNode(" 수 "); 007 L.insertLastNode(" 일 "); 008 L.printList(); 009 010 System.out.println("(2) 수노드뒤에금노드삽입하기 "); 011 ListNode pre = L.searchNode(" 수 "); 012 if(pre == null) 013 System.out.println(" 검색실패 >> 찾는데이터가없습니다."); 014 else{ 015 L.insertMiddleNode(pre, " 금 "); 016 L.printList(); 017 } 37
q 단순연결리스트 단순연결리스트프로그램 018 019 [ 예제 6-1] System.out.println("(3) 리스트의노드를역순으로바꾸기 "); 020 L.reverseList(); 021 L.printList(); 022 023 System.out.println("(4) 리스트의마지막노드삭제하기 "); 024 L.deleteLastNode(); 025 L.printList(); 026 } 027 } 028 029 class LinkedList{ 030 private ListNode head; 031 public LinkedList(){ 032 head = null; 033 } 034 public void insertmiddlenode(listnode pre, String data){ 035 ListNode newnode = new ListNode(data); 38
q 단순연결리스트 단순연결리스트프로그램 036 newnode.link = pre.link; 037 pre.link = newnode; 038 } 039 public void insertlastnode(string data){ 040 ListNode newnode = new ListNode(data); 041 if(head == null){ 042 this.head = newnode; 043 } 044 else{ 045 ListNode temp = head; 046 while(temp.link!= null) temp = temp.link; 047 temp.link = newnode; 048 } 049 } 050 public void deletelastnode(){ 051 ListNode pre, temp; 052 if(head == null) return; [ 예제 6-1] 39
q 단순연결리스트 단순연결리스트프로그램 053 if(head.link == null){ 054 head = null; 055 } 056 else{ 057 pre = head; 058 temp = head.link; 059 while(temp.link!= null){ 060 pre = temp; 061 temp = temp.link; 062 } 063 pre.link = null; 064 } 065 } 066 public ListNode searchnode(string data){ 067 ListNode temp = this.head; 068 while(temp!= null){ 069 if(data == temp.getdata()) [ 예제 6-1] 40
q 단순연결리스트 단순연결리스트프로그램 070 return temp; 071 else temp = temp.link; 072 } 073 return temp; 074 } 075 public void reverselist(){ 076 ListNode next = head; 077 ListNode current = null; 078 ListNode pre = null; 079 while(next!= null){ 080 pre = current; 081 current = next; 082 next = next.link; 083 current.link = pre; 084 } 085 head = current; 086 } [ 예제 6-1] 41
q 단순연결리스트 단순연결리스트프로그램 087 public void printlist(){ 088 ListNode temp = this.head; 089 System.out.printf("L = ("); 090 while(temp!= null){ 091 System.out.printf(temp.getData()); 092 temp = temp.link; 093 if(temp!= null){ 094 System.out.printf(", "); 095 } 096 } 097 System.out.println(")"); 098 } 099 } 100 101 class ListNode{ 102 private String data; 103 public ListNode link; [ 예제 6-1] 42
q 단순연결리스트 단순연결리스트프로그램 104 public ListNode(){ 105 this.data = null; 106 this.link = null; 107 } 108 public ListNode(String data){ 109 this.data = data; 110 this.link = null; 111 } 112 public ListNode(String data, ListNode link){ 113 this.data = data; 114 this.link = link; 115 } 116 public String getdata(){ 117 return this.data; 118 } 119 } [ 예제 6-1] 43
q 원형연결리스트 v 원형연결리스트 (circular linked list) 단순연결리스트에서마지막노드가리스트의첫번째노드를가리키게하여리스트의구조를원형으로만든연결리스트 단순연결리스트의마지막노드의링크필드에첫번째노드의주소를저장하여구성 링크를따라계속순회하면이전노드에접근가능 100번지 200번지 300번지 200 300 100 100 L... 44
q 원형연결리스트 v 원형연결리스트의삽입연산 마지막노드의링크를첫번째노드로연결하는부분만제외하고는단순연결리스트에서의삽입연산과같은연산 첫번째노드로삽입하기 원형연결리스트 CL 에 x 값을갖는노드 new 를삽입하는알고리즘 insertfirstnode(cl, x) new getnode(); new.data x; if (CL = null) then { // ❶ CL new; // ❶-a new.link new; // ❶-b } else{ // ❷ temp CL; // ❷-a while (temp.link CL) do // ❷-b temp temp.link; [ 알고리즘 6-8] new.link temp.link; // ❷-c temp.link new; // ❷-d CL new; // ❷-e } end insertfirstnode() 45
q 원형연결리스트 Ø 원형리스트가공백리스트인경우 삽입하는노드 new 는리스트의첫번째노드이자마지막노드가되어야함 [ 초기상태 ] CL null new 700 700 번지 x 1 CL new; 포인터 CL 이노드 new 를가리키게한다. CL 700 new 700 700 번지 x 2 new.link new; 노드 new 가자기자신을가리키게함으로써노드 new 를첫번째노드이자마지막노드가되도록지정한다. CL 700 new 700 700 번지 x 700 46
q 원형연결리스트 Ø 원형리스트가공백리스트가아닌경우 1 temp CL; 리스트가공백리스트가아닌경우에는첫번째노드의주소를임시순회포인터 temp 에저장하여노드순회의시작점을지정한다. CL 100 100번지 200번지 300번지 200 300 100 100 temp 2 while (temp.link CL) do temp temp.link; while 반복문을수행하여순회포인터 temp 를링크를따라마지막노드까지이동 CL 100 100 번지 200 200 번지 300 300 번지 100 100 temp 200 temp 300 temp 47
q 원형연결리스트 3 new.link temp.link; 리스트의마지막노드의링크값을노드 new 의링크에저장하여, 노드 new 가노드 temp 의다음노드를가리키게한다. 리스트 CL 은원형연결리스트이므로마지막노드의다음노드는리스트의첫번째노드가된다. CL 100 100번지 200번지 300번지 200 300 100 700번지 new 700 x 100 300 temp 4 temp.link new; 포인터 new 의값을포인터 temp 가가리키고있는마지막노드의링크에저장하여, 리스트의마지막노드가노드 new 를가리키게한다. CL 100 100번지 200번지 300번지 700번지 new 700 x 100 200 300 300 temp 700 48
q 원형연결리스트 5 CL new; 노드 new 의주소를리스트포인터 CL 에저장하여노드 new 가리스트의첫번째노드가되도록지정 CL 700 100 번지 200 200 번지 300 300 번지 700 700번지 new 700 x 100 300 temp [ 알고리즘 6-8] 실행결과 CL 700 700번지 x 100 100 번지 200 200 번지 300 300 번지 700 49
q 원형연결리스트 중간노드로삽입하기 원형연결리스트 CL 에 x 값을갖는노드 new 를포인터 pre 가가리키는 노드의다음노드로삽입하는알고리즘 insertmiddlenode(cl, pre, x) new getnode(); new.data x; if (CL=null) then { // ❶ CL new; new.link new; } else { // ❷ new.link pre.link; // ❷-a pre.link new; // ❷-b } end insertmiddlenode() [ 알고리즘 6-9] 50
q 원형연결리스트 1 new.link pre.link; 노드 pre 의다음노드로 new 를삽입하기위해서, 먼저노드 pre 의다음노드 (pre.link) 를 new 의다음노드 (new.link) 로연결 CL 100 100 번지 200 번지 300 번지 200 300 400 400 번지 100 pre 200 new 700 700 번지 x 300 51
q 원형연결리스트 2 pre.link new; 노드 new 의주소를노드 pre 의링크에저장하여, 노드 pre 가노드 new 를가리키 도록한다. CL 100 100 번지 200 200 번지 300 번지 700 400 400 번지 100 pre 200 new 700 700 번지 x 300 52
q 원형연결리스트 v 원형연결리스트의삭제연산 원형연결리스트 CL에서포인터 pre가가리키는노드의다음노드를삭제하고삭제한노드는자유공간리스트에반환하는연산 포인터 old 는삭제할노드지시 deletenode(cl, pre) if (CL = null) then error; else { old pre.link; // ❶ pre.link old.link; // ❷ if (old = CL) then // ❸ CL old.link; // ❸-a returnnode(old); // ❹ } end deletenode() [ 알고리즘 6-10] 53
q 원형연결리스트 1 old pre.link; 노드 pre 의다음노드를삭제할노드 old 로지정 CL 100 100 번지 200 200 번지 300 번지 300 400 400 번지 100 pre 200 old 300 2 pre.link old.link; 노드 old 의이전노드와다음노드를서로연결 CL 100 100 번지 200 번지 300 번지 200 400 400 400 번지 100 pre 200 old 300 54
q 원형연결리스트 Ø 삭제할노드 old 가리스트포인터 CL 인경우 1 CL old.link; 첫번째노드를삭제하는경우에는노드 old 의링크값을리스트포인터 CL 에저장하여두번째노드가리스트의첫번째노드가되도록조정 CL 200 100 번지 200 200 번지 300 번지 300 400 400 번지 200 old 100 pre 400 55
q 이중연결리스트 v 이중연결리스트 (doubly linked list) 양쪽방향으로순회할수있도록노드를연결한리스트 이중연결리스트의노드구조 두개의링크필드와한개의데이터필드로구성 llink(left link) 필드 : 왼쪽노드와연결하는포인터 rlink(right link) 필드 : 오른쪽노드와연결하는포인터 노드구조에대한구조체정의 public class DblNode{ DblNode llink; String data; DblNode rlink; } ; 56
q 이중연결리스트 단순연결기차 이중연결기차 57
q 이중연결리스트 리스트 week=( 월, 수, 금 ) 의이중연결리스트구성 원형이중연결리스트 이중연결리스트를원형으로구성 58
q 이중연결리스트 양방향기차만들기준비 59
q 이중연결리스트 양방향기차만들기 1 : 왼쪽사람의오른손이름표받기 60
q 이중연결리스트 양방향기차만들기 1 : 왼쪽사람에게자기이름주기 61
q 이중연결리스트 양방향기차만들기 2 : 오른쪽사람의왼손이름표받기 62
q 이중연결리스트 양방향기차만들기 2 : 오른쪽사람에게자기이름주기 63
q 이중연결리스트 양방향기차만들기 : 완성 64
q 이중연결리스트 이중연결리스트에서의삽입연산과정 ❶ 삽입할노드를가져온다. ❷ 새노드의데이터필드에값을저장한다. ❸ 새노드의왼쪽노드의오른쪽링크 (rlink) 를새노드의오른쪽링크 (rlink) 에저장한다. ❹ 그리고왼쪽노드의오른쪽링크 (rlink) 에새노드의주소를저장한다. ❺ 새노드의오른쪽노드의왼쪽링크 (llink) 를새노드의왼쪽링크 (llink) 에저장한다. ❻ 그리고오른쪽노드의왼쪽링크 (llink) 에새노드의주소를저장한다. 65
q 이중연결리스트 이중연결리스트에서의삽입알고리즘 insertnode(dl, pre, x) new getnode(); new.data x; new.rlink pre.rlink ; pre.rlink new; new.llink pre; new.rlink.llink new; end insertnode() // ❶ // ❷ // ❸ // ❹ [ 알고리즘 6-11] 66
q 이중연결리스트 이중연결리스트 DL 에서포인터 pre 가가리키는노드의다음노드 로노드 new 를삽입하는과정 초기상태 67
q 이중연결리스트 1 new.rlink pre.rlink ; 노드 pre 의 rlink 를노드 new 의 rlink 에저장하여, 노드 pre 의오른쪽노드를삽입 할노드 new 의오른쪽노드로연결 68
q 이중연결리스트 2 pre.rlink new; 새노드 new 의주소를노드 pre 의 rlink 에저장하여, 노드 new 를노드 pre 의오른 쪽노드로연결 69
q 이중연결리스트 3 new.llink pre; 포인터 pre 의값을삽입할노드 new 의 llink 에저장하여, 노드 pre 를노드 new 의 왼쪽노드로연결 70
q 이중연결리스트 4 new.rlink.llink new; 포인터 new 의값을노드 new 의오른쪽노드 (new.rlink) 의 llink 에저장하여, 노드 new 의오른쪽노드의왼쪽노드로노드 new 를연결 71
q 이중연결리스트 삭제 : 오른손이름표넘겨주기 72
q 이중연결리스트 삭제 : 왼손이름표넘겨주기 73
q 이중연결리스트 삭제완료 74
q 이중연결리스트 이중연결리스트에서의삽입연산과정 ❶ 삭제할노드의오른쪽노드의주소 (old.rlink) 를삭제할노드의왼쪽노드 (old.llink) 의오른쪽링크 (rlink) 에저장한다. ❷ 삭제할노드의왼쪽노드의주소 (old.llink) 를삭제할노드의오른쪽노드 (old.rlink) 의왼쪽링크 (llink) 에저장한다. ❸ 삭제한노드를자유공간리스트에반환한다. 이중연결리스트에서의삭제알고리즘 deletenode(dl, old) old.llink.rlink old.rlink; // ❶ old.rlink.llink old.llink; // ❷ returnnode(old); // ❸ end deletenode( ) [ 알고리즘 6-12] 75
q 이중연결리스트 이중연결리스트 DL 에서포인터 old 가가리키는노드를삭제하는 과정 초기상태 76
q 이중연결리스트 1 old.llink.rlink old.rlink; 삭제할노드 old 의오른쪽노드의주소를노드 old 의왼쪽노드의 rlink 에저장하여, 노드 old 의오른쪽노드를노드 old 의왼쪽노드의오른쪽노드로연결 77
q 이중연결리스트 2 old.rlink.llink old.llink; 삭제할노드 old 의왼쪽노드의주소를노드 old 의오른쪽노드의 llink 에저장하여, 노드 old 의왼쪽노드를노드 old 의오른쪽노드의왼쪽노드로연결 78
q 이중연결리스트 3 returnnode(old); 삭제된노드 old 는자유공간리스트에반환 79
q 다항식의연결자료구조표현 v 단순연결리스트를이용하여다항식표현 다항식의항 : 단순연결리스트의노드 노드구조 각항에대해서계수와지수를저장 계수를저장하는 coef 와지수를저장하는 expo 의두개의필드로구성 링크필드 : 다음항을연결하는포인터로구성 노드에대한구조체정의 public class Node { float coef; int expo; Node link; }; 80
q 다항식의연결자료구조표현 다항식의단순연결리스트표현예 다항식 A(x)=4x 3 +3x 2 +5x 다항식 B(x)=3x 4 +x 3 +2x+1 81
q 다항식의연결자료구조표현 v 다항식연결자료구조의삽입연산 다항식에항을추가하는알고리즘 Ø 다항식리스트포인터 PL, coef 필드값을저장한변수 coef, expo 필드값을저장한변수 expo 리스트 PL 의마지막노드의위치를지시하는포인터 last 사용 appendterm(pl, coef, expo, last) new getnode( ); new.expo expo; new.coef coef; new.link null; if (PL = null) then { // ❶ PL new; // ❶-a last new; // ❶-b } else { // ❷ last.link new; // ❷-a last new; // ❷-b } end appendterm( ) [ 알고리즘 6-13] 82
q 다항식의연결자료구조표현 공백다항식에서의항삽입연산 초기상태 1 PL new; 포인터 new 의값을리스트포인터 PL 에저장하여, 노드 new 가리스트 PL 의첫번째노드가되도록연결 2 last new; 포인터 new 의값을포인터 last 에저장하여, 포인터 last 가리스트 PL 의마지막노드인노드 new 를가리키도록지정 83
q 다항식의연결자료구조표현 다항식에서의항삽입연산 초기상태 1 last.link new; 포인터 new 의값을노드 last 의링크에저장하여, 노드 new 를노드 last 의다음 노드로연결 84
q 다항식의연결자료구조표현 2 last new; 포인터 new 의값을포인터 last 에저장하여, 노드 new 를리스트 PL 의마지막노 드로지정 85
q 다항식의연결자료구조표현 다항식리스트 A 에 appendterm() 알고리즘을사용하여 2x 0 항 ( 상수항 2) 추가예 86
q 다항식의연결자료구조표현 v 다항식의덧셈연산 덧셈 A +B =C 를단순연결리스트자료구조로연산 Ø 다항식 A 와 B, C 의항을지시하기위해서세개의포인터를사용 Ø 포인터 p : 다항식 A 에서비교할항을지시 Ø 포인터 q : 다항식 B 에서비교할항을지시 Ø 포인터 r : 덧셈연산결과만들어지는다항식 C 의항을지시 1 p.expo < q.expo : 다항식 A 항의지수가작은경우 포인터 q 가가리키는다항식 B 의항을 C 의항으로복사 q 가가리키는항에대한처리가끝났으므로 q 를다음노드로이동 87
q 다항식의연결자료구조표현 88
q 다항식의연결자료구조표현 2 p.expo = q.expo : 두항의지수가같은경우 p.coef와 q.coef를더하여 C 의항, 즉 r.coef에저장하고지수가같아야하므로 p.expo( 또는 q.expo) 를 r.expo에저장 다음항을비교하기위해포인터 p와 q를각각다음노드로이동 89
q 다항식의연결자료구조표현 3 p.expo > q.expo : 다항식 A 항의지수가큰경우 포인터 p 가가리키는다항식 A 의항을 C 의항으로복사 p 가가리키는항에대한처리가끝났으므로 p 를다음노드로이동 90
q 다항식의연결자료구조표현 다항식의덧셈알고리즘 addpoly(a, B) [ 알고리즘 6-14] // 단순연결리스트로표현된다항식 A와 B를더하여새로운다항식 C를반환 p A; q B; C null; // 결과다항식 r null; // 결과다항식의마지막노드를지시 while (p null and q null) do { // p, q는순회용참조변수 case { p.expo = q.expo : sum p.coef + q.coef if (sum 0) then appendterm(c, sum, p.expo, r); p p.link; q q.link; p.expo < q.expo : appendterm(c, q.coef, q.expo, r); q q.link; 91
q 다항식의연결자료구조표현 다항식의덧셈알고리즘 else : // p.expo > q.expo인경우 appendterm(c, p.coef, p.expo, r); p p.link; } // end case } // end while [ 알고리즘 6-14] while (p null) do { // A의나머지항들을 C에복사 appendterm(c, p.coef, p.expo, r); p p.link; } while (q null) do { // B의나머지항들을 C에복사 appendterm(c, q.coef, q.expo, r); q q.link; } return C; end addpoly() 92
q 다항식의연결자료구조표현 다항식의덧셈예 A(x)=4x 3 +3x 2 +5x B(x)=3x 4 +x 3 +2x+1 초기상태 93
q 다항식의연결자료구조표현 1 4x 3 항과 3x 2 항에대한처리 p.expo < q.expo 이므로지수가큰 q 노드를리스트 C 에복사 포인터 q 는다음노드로이동 94
q 다항식의연결자료구조표현 2 4x 3 항과 1x 3 항에대한처리 p.expo = q.expo 이므로두노드의 coef 필드의값을더하고, expo 필드의값을복사한노드를리스트 C 에추가 포인터 p 와 q 는다음노드로이동 95
q 다항식의연결자료구조표현 3 3x 2 항과 2x 1 항에대한처리 p.expo > q.expo 이므로지수가큰 p 노드를리스트 C 에복사 포인터 p 는다음노드로이동 96
q 다항식의연결자료구조표현 4 5x 1 항과 2x 1 항에대한처리 p.expo = q.expo 이므로두노드의 coef 필드의값을더하고, expo 필드의값을복사한노드를리스트 C 에추가 포인터 p 와 q 는다음노드로이동 97
q 다항식의연결자료구조표현 5 B(x) 의남은항에대한처리 포인터 p가 null이므로다항식 A 의항에대한처리끝 처리할항이남아있는다항식 B 의포인터 q는 null이될때까지모든노드를복사하여리스트 C에추가 98
IT CookBook 자바로배우는쉬운자료구조 6 장끝