더블 링크드 리스트

#1. 프로시험에 유용한 - 동적할당 대신 사용할수 있는 배열

#2. 프로시험에 유용한 - Hash 사용법

#3. 프로시험에 유용한 - 트리 사용법 (자연수 ID 를 가지는 트리)

#4. 프로시험에 유용한 - 트리 사용법

#5. 프로시험에 유용한 - Graph 사용법

#6. 프로시험에 유용한 - 더블 링크드 리스트

어쩌다 보니 같은 코드로만 6번째 글까지 쓰게 되었네요.

이번에는 더블 링크드 리스트입니다.

지금까지 보여드렸던 Single Linked List 는 아래와 같은 그림으로 설명됩니다.

(복습이 아니라 더블 링크드 리스트에 필요해서 다시 한번 작성합니다.)

                                                              

- NODE* 인 pList 는 초기화시에 NULL

1	pList = NULL;

                               

- NODE 1을 추가시에 pList가 가르키는 것을 Node 1의 prev가 가르킴

- pList 는 추가되는 노드를 가르킴

1 2	node1->prev = pList;   //빨간선 pList = node1  //초록선

- NODE 2가 추가 되는 경우 동일하게 반복됩니다.

- pList 가 가르키던 건 Node 2의 prev가 가르킴

- pList 는 추가된 Node 2를 가르킴

1 2	node2->prev = pList;  //초록선 pList = node2;  //주황선

추가되는 노드는 항상 Single linked list 에서 뒤쪽으로 추가됩니다.

Node 내의 prev 라고 이름 지어진 이유이기도 하구요.

==============================================

위의 Single linked list 를 바탕으로 더블 링크드 리스트를 설명드리면

초기에는 Head 와 Tail 두개의 Node를 미리 가지고 있습니다.

(이하 그림에서 빨간선으로 연결된 부분이 싱글 링크드 리스트와 동일합니다.)

                                                                 

- 초기화로 head의 next 는 tail을    tail 의 prev 는 head 를 가르킵니다.

1 2 3 4

NODE *head = myalloc(); NODE *tail = myalloc(); head->next = tail; tail->prev = head;

tail->prev 가 싱글링크드리스트의 pList 역할을 하고 있으므로

노드가 추가되면  tail의 prev에 추가하시면 됩니다.

                   

1 2 3 4 5 6

NODE *node1 = myalloc(); node1->v = 1;     node1->prev = tail->prev;  //tail->prev 가 가르키던것은 내가 가르키고 tail->prev = node1;   //tail->prev 는 나를 가르키게

여기까지가 싱글링크드리스트와 동일하게 빨간선 연결을 해준것입니다.

이후 초록색인 next 연결을 처리하면 됩니다.

1 2	node1->next = node1->prev->next;   // 나의 next는  prev노드가 가르키던 next를 node1->prev->next = node1;    //prev 노드의 next는 나를 가르키게

- 주의하실 점은 추가되는 node1 의 prev, next 를 먼저 지정해야 합니다. (너무 당연한 말이지만요)

두번째 노드를 추가하면 동일과정을 반복하면 됩니다.

1 2 3 4 5 6 7 8 9 10

NODE * node2 = myalloc(); node2->v = 2;     node2->prev = tail->prev; tail->prev = node2;     node2->next = node2->prev->next; node2->prev->next = node2;

이제 검색하실 때는 head 에서 tail 까지  혹은 tail 에서 head 까지 검색하실 수 있습니다.

먼저 Head 에서 Tail 로 검색하는 경우

출발점은 head->next, 끝나는 점은 tail 까지 가시면 됩니다.

1 2 3 4 5 6

for(NODE* iter = head->next; iter != tail; iter = iter->next) {     if(iter->v == 1) cout << "Found.. " << iter->i;     }

다음으로 Tail 에서 Head로 검색하는 경우

출발점은 tail->prev, 끝나는 점은 head 가 되겠네요.

1 2 3 4

for(NODE *iter = tail->prev; iter != head; iter = iter->prev) {     if(iter->v == 1) cout << "Found.. " << iter->i; }

이제 삭제하는 방법입니다.

2번 노드를 검색해서 삭제하는 경우, 아래와 같이 노드의 연결만 변경하면 됩니다.

(기존의 Node2 가 가진 연결은 안 지워도 됩니다. (그림은 보기 쉽게 지웠습니다.)

1 2 3 4 5 6 7 8 9 10

for(NODE *iter = head->next; iter != tail; iter = iter->next) {     if(iter->v == 2)     {         iter->prev->next = iter->next;    // prev 노드의 next를  내가 가르키던 next 로  (초록색연결)         iter->next->prev = iter->prev;    // next 노드의 prev를  내가 가르키던 prev 로  (빨간색연결)     }     }

#싱글 링크드 리스트도 pList 대신 dummy node 인 Tail 노드를 미리 만들어 두고 사용하면 삭제시에 좀더 쉽습니다.

#hash와 single linked list 를 같이 사용하면  이번 페이지단어검색에 대한 해결이 될수도 있을 것같네요.

#Pro 시험에 나오는 문제도 hash, single linked list, double linked list, tri 등등 여러가지를 함께 사용해야

  해결이 가능한 문제가 앞으로 많이 나올 것 같습니다.

* 같은 포멧의 코드를 계속 사용해서

* 실수할 가능성을 줄이고

* 코딩 속도는 빠르게 해 줍니다.

** 많은 추천 부탁드려요

==============

Dummy tail 을 추가한 싱글 링크드 리스트의 삭제편입니다.

#include <iostream> using namespace std; struct NODE { int v; NODE * prev; //싱글 리스트를 위해 추가. } a[20000]; int arr_idx = 0; NODE *myalloc(void) { return &a[arr_idx++]; } void main(void) { arr_idx = 0; //사용할 배열 초기화 NODE *tail = myalloc(); //Dummy tail 노드를 미리 만들어 둡니다. tail->prev = nullptr; //tail->prev 가 pList 역할을 대신 합니다. NODE *p; for (int i = 0; i<8; i++) { p = myalloc(); p->v = i; p->prev = tail->prev; // tail->prev 에 추가합니다. tail->prev = p; } //추가된 모든 노드 확인. for (NODE *iter = tail->prev; iter != nullptr; iter = iter->prev) { cout << iter->v << " "; } cout << endl; // 5를 찾아서 삭제 NODE * next = tail; //노드 저장은 tail 부터 for (NODE *iter = tail->prev; iter != nullptr; iter = iter->prev) { if (iter->v == 5) //5를 찾으면 { cout << "Deleted " << iter->v << endl; next->prev = iter->prev; //저장해둔 노드의 prev를 변경하여 삭제 } next = iter; //노드를 저장합니다. } cout << endl; //삭제후 모든 노드 확인. for (NODE *iter = tail->prev; iter != nullptr; iter = iter->prev) { cout << iter->v << " "; } cout << endl; }

double_linked_list

#include <iostream> using namespace std; int arr_idx = 0; struct NODE { int v; NODE * prev; //for single linked list NODE * next; //for double linked list } a[20000]; NODE *myalloc(void) { return &a[arr_idx++]; } NODE * pTail; //더블 링크드 리스트의 끝. (싱글 링크드 리스트의 pList의 역활) NODE * pHead; //더블 링크드 리스트의 시작. void print_node(void); int main(void) { arr_idx = 0; //사용할 배열 초기화 pHead = myalloc(); //Head 노드를 미리 만들어둠. pTail = myalloc(); //Tail 노드를 미리 만들어둠. pTail->prev = pHead; //pHead <-> pTail 을 연결 pHead->next = pTail; NODE *p; // 노드 추가.. for (int i = 1; i < 10; i++) { p = myalloc(); p->v = i; p->prev = pTail->prev; //기존 싱글 리스트 연결 방식과 동일(저장 위치만 pTail->prev 로 바뀜) pTail->prev = p; //next 연결. p->next = p->prev->next; //이전노드가 가르키던걸 내가 가르키고. p->prev->next = p; //이전 노드는 나를 가르키게 만듬. } print_node(); //HEAD 부터 검색해서 노드(5) 삭제 for (NODE * iter = pHead->next; iter != pTail; iter = iter->next) //HEAD 에서 모든 노드를 따라가면서.. { if (iter->v == 5) //노드(5)를 찾으면 { iter->prev->next = iter->next; //이전 노드의 다음(next)은 내가 가르키던 다음(next)을 iter->next->prev = iter->prev; //다음 노드의 이전(next)은 내가 가르키던 이전(prev)을 cout << "Delete 5 node ... " << endl << endl; } } print_node(); //TAIL 부터 검색해서 노드(3) 삭제 for (NODE * iter = pTail->prev; iter != pHead; iter = iter->prev) //TAIL 에서 모든 노드를 따라가면서.. { if (iter->v == 3) //노드(3)를 찾으면 { iter->prev->next = iter->next; //이전 노드의 다음(next)은 내가 가르키던 다음(next)을 iter->next->prev = iter->prev; //다음 노드의 이전(next)은 내가 가르키던 이전(prev)을 cout << "Delete 3 node ... " << endl << endl; } } print_node(); //TAIL 부터 검색해서 모든노드 삭제 for (NODE * iter = pTail->prev; iter != pHead; iter = iter->prev) //TAIL 에서 모든 노드를 따라가면서.. { iter->prev->next = iter->next; //이전 노드의 다음(next)은 내가 가르키던 다음(next)을 iter->next->prev = iter->prev; //다음 노드의 이전(next)은 내가 가르키던 이전(prev)을 cout << "Delete node ... " << iter->v << endl << endl; } print_node(); //다시 노드 추가.. for (int i = 1; i < 10; i++) { p = myalloc(); p->v = i; p->prev = pTail->prev; //기존 싱글 리스트 연결 방식과 동일(저장 위치만 pTail->prev 로 바뀜) pTail->prev = p; //next 연결. p->next = p->prev->next; //이전노드가 가르키던걸 내가 가르키고. p->prev->next = p; //이전 노드는 나를 가르키게 만듬. } print_node(); } void print_node(void) { cout << "From head ~~ " << endl; for (NODE * iter = pHead->next; iter != pTail; iter = iter->next) cout << iter->v << " "; cout << endl; cout << "From tail ~~ " << endl; for (NODE * iter = pTail->prev; iter != pHead; iter = iter->prev) cout << iter->v << " "; cout << endl << endl; }