Double Linked List

0. 자료구조를 하기 앞서

1. http://www.acmicpc.net 에 가입 되어 있지 않다면 가입한다. (이메일 인증이 있다면 이메일 인증까지)

2. https://www.acmicpc.net/group/3060 를 들어가서 가입 신청을 누른다.

3. 연습 문제란에 있는 문제를 풀어본다.

(어려운 문제가 아닌 위의 사이트에서 입 출력을 어떻게 해서 문제를 어떻게 푸는지 알려주기위함)

1. 연결 리스트 사용이유?

- 연결 리스트는 배열과 같이 크기가 정해져 있는 자료구조와 달리 메모리를 동적으로 사용할 수 있다는 장점이 있다.

- 연결 리스트개념을 알아야 포인터를 자유자제로 잘 다룰 수 있고, 추후에 배울 트리, 그래프 코딩을 잘 할 수 있다.

** 참고 **

int arr[100];같은 것을 인접 행렬이라하고, 포인터를 이용하여 리스트로 이루어 진것을 인접 리스트라 한다.

2. 이중 연결리스트

이제 연결리스트가 무엇인지 알았으니 이중 연결리스트를 배워보도록 한다.

** 아니 연결리스트도 안하고 이중 연결리스트를 한다구요?? **

지금 이 시간을 통해 이중 연결리스트를 배우면 연결 리스트는 자동으로 따라오게 된다.

따라서 연결 리스트를 넘기고 이중 연결리스트를 바로 배워보도록 하자.

심지어 여기서는 더미노드가 있는 이중 연결리스트를 만들어 볼 것이다.

더미노드 생성 이유?

1. 더미노드가 있으면 이중 연결리스트에서 head와 tail이 움직일 필요가 없어진다.

2. 삽입/삭제 시 코드가 간결해지고 논리가 쉬워진다.

등등.. 연결리스트에 더미노드가 필요한 이유

(스스로 해보기)

직접 더미노드가 없는 이중 연결리스트를 제작해보자.

그리고 뭐때문에 더미더미 거리는지 한번 확인해보자.

http://www.crocus.co.kr/342 (더미노드가 없는 이중 연결 리스트 설명)

http://www.crocus.co.kr/343?category=150836 (더미노드가 없는 이중 연결 리스트 코드)

3. 더미 노드가 있는 이중 연결 리스트 그림

(더미 노드의 유무 차이를 위의 그림을 통해 이해해보자)

4. 더미 노드가 있는 이중 연결 리스트 코드

1. struct로 짜도 되고 class로 짜도 된다.

2. friend class LIST를 통해 NODE 클래스의 private값을 LIST 클래스가 이용 할 수 있게 된다.

3. 생성자 소멸자 주석을 지워서 생성자 소멸자가 호출되는 것도 한번 보자.

아래 코드를 짜보고 main부분과 all 부분을 적절히 수정하여 https://www.acmicpc.net/problem/11720 문제를 풀어보자.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163

#include <iostream> #include <cstdio>   using namespace std;   class NODE{     friend class LIST;   private:     int data;     NODE *left;     NODE *right; };   class LIST { private:     NODE *head;     NODE *tail;      public:     LIST(){         //cout << "\n\n생성자 호출\n\n" << endl;         NODE *dummyHead = new NODE;         NODE *dummyTail = new NODE;           dummyHead->left = dummyHead->right = NULL;         dummyTail->left = dummyTail->right = NULL;           head = dummyHead;         tail = dummyTail;     }       ~LIST() {          init();         delete head;         delete tail;           //cout << "\n\n소멸자 호출\n\n " << endl;      }       void init() {         // 더미노드 사이 모든 값 삭제         NODE *pos = head;         while (pos->right != NULL)         {             NODE *delNode = pos;             pos = pos->right;               delete delNode;         }         delete tail; // 마지막 tail이 삭제되지 않았다.           // 더미노드 새로 생성(생성자와 동일)         NODE *dummyHead = new NODE;         NODE *dummyTail = new NODE;           dummyHead->left = dummyHead->right = NULL;         dummyTail->left = dummyTail->right = NULL;           head = dummyHead;         tail = dummyTail;     }     void insert(int val) {         // 리스트가 형성되어 있지 않았을 때         if (head->right == NULL)         {             NODE *newNode = new NODE;             newNode->data = val;               newNode->left = head;             head->right = newNode;                          newNode->right = tail;             tail->left = newNode;         }           else         {             NODE *newNode = new NODE;             newNode->data = val;                          newNode->left = tail->left;             tail->left->right = newNode;               newNode->right = tail;             tail->left = newNode;         }     }     void del(int val) {         NODE *pos = head;         bool isFind = false;         while (pos->right != NULL)         {             if (pos->data == val)             {                 pos->left->right = pos->right;                 pos->right->left = pos->left;                 delete pos;                 isFind = true;                 break;             }             pos = pos->right;         }           if (!isFind)             cout << "삭제할 데이터가 없습니다." << endl;     }       void all() {         NODE *pos = head;         while (pos != NULL)         {             // 더미노드는 출력하지 않는다.             if (!(pos == head || pos == tail))                 cout << pos->data << " ";                      pos = pos->right;         }         cout << endl;     } }; int main() {     LIST list;       while (1)     {         int num;         cout << "1 :: 초기화\n2 :: 추가\n3 :: 삭제\n4 :: 전체출력\n5 :: 종료\n입력 :: ";         cin >> num;           if (num == 1)             list.init();           else if (num == 2)         {             int val;             cout << "값 :: ";             cin >> val;             list.insert(val);         }           else if (num == 3)         {             int val;             cout << "값 :: ";             cin >> val;             list.del(val);         }           else if (num == 4)             list.all();                  else if (num == 5)             break;                  cout << endl;     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus