[C++] Doubly Linked List 이중 연결 리스트 구현

Doubly Linked List 이중 연결 리스트 구현

 

Doubly Linked List 는 무엇일까?

Singly Linked List (단순 연결 리스트) 는 노드 사이의 연결이 단방향 이다. 하지만 Doubly Linked List  (이중 연결 리스트)는 노드 사이의 연결이 양방향이다. 각각의 노드는 다음 노드에 대한 연결뿐만 아니라 이전 노드에 대한 연결도 가지고 있다. 그렇기 때문에 Doubly Linked List는 이전 노드, 다음 노드로의 접근이 모두 가능하다.

 

Doubly Linked List의 노드 구조

 

Doubly Linked List의 구조

첫번째 노드는 이전 노드가 없기 때문에 이전 노드에 대한 링크는 NULL 이다. 또한, 마지막 노드는 다음 노드가 없기 때문에 다음 노드에 대한 링크는 NULL 이다.

 

Doubly Linked List의 장점

• 전후방향 모두 접근이 가능하다.
• 주어진 노드 앞에 새로운 노드를 빠르게 삽입할 수 있다.
• 삭제할 노드의 포인터가 주어질때 삭제 작업이 효율적이다.
• 노드를 탐색하는것이 빠르다.
  • Singly Linked List는 특정한 노드를 찾기 위해서 탐색을 할때 모든 노드를 탐색해야하는 경우가 생긴다.

 

Doubly Linked List의 단점

1. 모든 노드가 previous 포인터를 위한 추가 공간을 필요로 한다.
   • 더 많은 메모리가 필요하다.
2. 모든 Operation은 previous 포인터를 필요로 한다.
   • Next 포인터 뿐만 아니라 Previous 포인터까지 신경써주어야 한다.

새로운 노드를 생성할때

1. Doubly Linked List에서 새로운 자료를 추가할때 새로운 노드를 생성해야 한다.
2. 새로운 노드의 링크에 이전 노드와 다음 노드를 연결해주어야 한다,
3. 마지막으로 기존 노드의 링크를 재지정 해주어야 한다.

기존 노드를 제거할때

1. 제거하려는 노드의 이전 노드를 찾고, '이전 노드의 링크'를 '제거하고자 하는 노드'의 '다음 노드'로 재지정 한다.
2. 메모리를 지정해주었다면 메모리를 해제

 

Implementation 구현

Github