[자료구조] 이중 연결리스트(doubly linked list)

 

단일 연결리스트(singly linked list)의 문제점

 

• 임의의 노드를 삭제할 경우, 전위 노드의 위치를 파악해야 함
• 리스트의 각 노드를 접근하고 할 때, 연결의 방향으로 쉽게 이동할 수 있으나 특정 노드의 전위노드를 접근하고자 할 경우 처음부터 다시 연결을 따라 차례대로 접근해야 함

 

이중 연결리스트(doubly linked list)의 구조

 

• 하나의 노드에 한 개 이상의 연결필드(임의 노드를 중심으로 전위/후위 노드의 위치에 대한 포인터)를 가짐
• 이중 연결리스트에서는 리스트를 양방향으로 이동할 수 있기 때문에 노드의 삽입/삭제가 편리함
• 공간(2개의 포인터)을 많이 차지하고 코드가 복잡함

 

이중 연결리스트의 메소드

 

• push(data) : 연결리스트의 마지막에 새로운 노드를 추가함
• pop() : 연결리스트의 마지막 노드를 제거하고 해당 값을 반환함
• shift() : 연결리스트의 첫번째 노드를 제거하고 해당 값을 반환함
• unshift() : 연결리스트의 맨 앞에 새로운 노드를 추가함
• get(index) : 지정된 인덱스의 노드 값을 반환함
• set(index, data) : 지정된 인덱스의 노드 값을 변경함
• insert(index, data) : 지정된 인덱스에 새로운 노드를 삽입함
• remove(index) : 지정된 인덱스의 노드를 제거하고 해당 값을 반환함

 

이중 연결리스트 역순 알고리즘

 

 

void reverse(struct Node **head_ref) {
   struct Node *temp = NULL;
   struct Node *current = *head_ref;
   while (current !=  NULL) {
     temp = current->prev;
     current->prev = current->next;
     current->next = temp;
     current = current->prev;
   }
   if(temp != NULL)
     *head_ref = temp->prev;
}