이중 연결 목록: C++, Python (코드 예)
사라 첸
이중 연결 목록이란 무엇입니까?
이중 연결 리스트에서는 각 노드가 이전 노드와 다음 노드에 대한 링크를 모두 갖습니다. 각 노드는 세 가지 요소로 구성됩니다. 하나는 데이터를 보유하고 다른 두 개는 다음 및 이전 노드의 포인터입니다. 이 두 포인터는 특정 노드에서 앞으로 또는 뒤로 이동하는 데 도움이 됩니다.
이중 연결 리스트의 기본 구조는 다음과 같습니다.
모든 연결리스트에는 헤드 노드와 테일 노드가 있습니다. 헤드 노드에는 "이전"(이전 포인터) 노드가 없고 테일 노드에는 "다음" 노드가 없습니다.
이중 연결 목록에 대한 몇 가지 중요한 용어는 다음과 같습니다.
- 이전 : 각 노드는 이전 노드에 연결됩니다. 포인터나 링크로 사용됩니다.
- 다음 : 각 노드는 다음 노드에 연결됩니다. 포인터나 링크로 사용됩니다.
- 날짜 : 이는 노드에 데이터를 저장하는 데 사용됩니다. "데이터"는 다른 데이터를 보유할 수 있습니다. 데이터 구조 그 안에. 예를 들어 문자열, 사전, 집합, 해시맵 등이 "데이터"에 저장될 수 있습니다.
이중 연결 리스트의 단일 노드의 기본 구조는 다음과 같습니다.
Opera이중 연결 목록의 종류
이중 연결 리스트의 연산에는 노드 추가 및 삭제, 노드 삽입 및 제거, 연결 리스트를 위에서 아래로 탐색하는 작업이 포함됩니다.
이중 연결 리스트를 사용하여 구현할 수 있는 연산 목록은 다음과 같습니다.
- 앞에 삽입
- 꼬리 또는 마지막 노드에 삽입
- 노드 뒤에 삽입
- 노드 앞에 삽입
- 앞에서 삭제
- 꼬리에서 삭제
- 노드 검색 및 삭제
- 머리에서 꼬리까지 횡단
- 꼬리에서 머리로 가로지르기
위의 모든 연산에 대한 구현과 의사코드를 살펴보겠습니다.
이중 연결 목록 앞에 삽입
앞에 삽입한다는 것은 연결된 목록에 노드를 만들고 연결 목록의 시작 부분에 배치해야 함을 의미합니다.
예를 들어, 주어진 노드 "15"가 있습니다. 이것을 헤드 노드에 추가해야 합니다.
이 작업을 수행할 때 중요한 조건은 두 가지입니다.
- 이중 연결 목록에 노드가 없으면 새 노드가 헤드 노드가 됩니다.
- 이미 헤드 노드가 있는 경우 이전 헤드가 새 노드로 대체됩니다.
이 작업에 대한 의사 코드는 다음과 같습니다.
function insertAtFront (ListHead, value): newNode = Node() newNode.value = value ListHead.prev = NewNode NewNode.next = ListHead newNode.prev = NULL return ListHead
이중 연결 목록 끝에 삽입
"끝에 삽입"은 연결 목록에 노드를 만들고 끝에 배치한다는 의미입니다.
이를 수행하기 위해 다음 두 가지 방법을 사용할 수 있습니다.
- 방법 1 : "다음"이 null이 될 때까지 이중 연결 목록의 선두부터 탐색을 시작합니다. 그런 다음 새 노드를 "다음"과 연결합니다.
- 방법 2 : 이중 연결 목록의 마지막 노드를 가져옵니다. 그런 다음 마지막 노드의 "다음" 노드가 새 노드에 연결됩니다. 이제 새 노드가 꼬리 노드가 됩니다.
꼬리 노드에 삽입하기 위한 의사 코드는 다음과 같습니다.
function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: then ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead
노드 뒤에 삽입
다음과 같은 이중 연결 리스트가 있다고 가정해 보겠습니다.
값이 "12"인 노드 뒤에 연결될 특정 노드를 삽입하려고 합니다.
이에 대한 단계는 다음과 같습니다.
단계 1) 헤드에서 마지막 노드까지 트래버스합니다. 어떤 노드의 값이 "12"인지 확인하십시오.
단계 2) 새 노드를 생성하고 이를 노드 "12"의 다음 포인터로 할당합니다. 새 노드의 "다음" 노드는 15가 됩니다.
이중 연결 리스트의 노드 뒤에 노드를 삽입하는 의사 코드는 다음과 같습니다.
function insertAfter(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.value is not equal searchItem then List = ListHead.next List = List.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
노드 앞에 삽입
이 작업은 "노드 뒤에 삽입"과 더 비슷합니다. 이를 수행하려면 특정 노드의 값을 검색해야 합니다. 그런 다음 새 노드를 생성하여 검색된 노드 앞에 삽입합니다.
노드 "15" 앞에 주어진 노드 "12"를 삽입하고 싶다고 가정해 보겠습니다. 그런 다음 이를 수행하는 단계는 다음과 같습니다.
단계 1) 헤드 노드에서 테일 노드까지 연결 리스트를 탐색합니다.
단계 2) 현재 노드의 다음 포인터의 값이 "12"인지 확인합니다.
단계 3) 새 노드를 현재 노드의 "다음" 노드로 삽입합니다.
이중 연결 목록의 노드 앞에 노드를 삽입하는 의사 코드는 다음과 같습니다.
function insertBefore(ListHead, searchItem, value): List = ListHead NewNode = Node() NewNode.value = value while List.next.value is not equal searchItem then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
이중 연결 리스트의 선두 삭제
이전 노드가 없는 이중 연결 리스트의 헤드 노드입니다. 따라서 헤드 노드를 삭제하려는 경우 다음 포인터는 새 헤드 노드가 됩니다. 또한 노드를 삭제하는 동안 노드가 차지하는 메모리를 해제해야 합니다.
헤드 노드를 삭제하는 단계는 다음과 같습니다.
단계 1) 현재 헤드 노드에 변수를 할당합니다.
단계 2) 현재 헤드 노드의 "다음" 노드를 방문하고 "이전"(이전 포인터) 노드를 ''NULL'로 만듭니다. 이는 첫 번째 노드에서 두 번째 노드의 연결을 끊는다는 의미입니다.
단계 3) 이전 헤드 노드가 점유한 메모리를 해제합니다.
이중 연결 리스트에서 헤드를 삭제하는 의사 코드는 다음과 같습니다.
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
모든 종류의 삭제 작업을 수행한 후에는 할당된 메모리를 삭제해야 합니다. 그렇지 않으면 프로그램의 전체 런타임 동안 삭제된 블록의 메모리가 점유된 상태로 유지됩니다. 다른 애플리케이션은 해당 메모리 세그먼트를 사용할 수 없습니다.
이중 연결 리스트의 꼬리를 삭제합니다.
이 작업은 헤드 삭제와 비슷합니다. 여기서는 헤드 대신 테일을 삭제해야 합니다. 노드를 테일 노드로 식별하려면 다음 포인터 또는 다음 노드가 null인지 확인해야 합니다. 테일을 삭제한 후에는 메모리를 해제해야 합니다.
이 작업은 "뒤에서 삭제"라고도 불립니다.
이를 수행하는 단계는 다음과 같습니다.
단계 1) 이중 연결 리스트의 꼬리 노드까지 순회합니다.
단계 2) 꼬리 노드에 변수나 포인터를 할당합니다.
단계 3) "다음" 노드를 NULL로 만들고 꼬리 노드의 메모리를 해제합니다.
꼬리 노드를 삭제하기 위한 의사 코드는 다음과 같습니다.
function DeleteTail( ListHead ): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead.next ListHead.next = NULL free memory( Tail ) return head
이중 연결 목록에서 노드 검색 및 삭제
이 연산을 통해 특정 노드 데이터를 검색하고 해당 노드를 삭제할 수 있습니다. 연결 리스트는 선형 데이터 구조이므로 선형 검색을 수행해야 합니다. 삭제한 후에는 메모리를 해제해야 합니다.
이중 연결 리스트에서 노드를 검색하고 삭제하는 단계는 다음과 같습니다.
단계 1) 노드의 값이 검색 항목과 같아질 때까지 헤드에서 연결된 목록을 탐색합니다.
단계 2) 일치하는 노드에 변수 “deleteNode”를 할당합니다.
단계 3) "deleteNode"의 이전 노드를 다음 노드에 할당합니다.
단계 4) "deleteNode"의 메모리를 해제합니다.
연결 리스트에서 노드를 검색하고 삭제하기 위한 의사코드는 다음과 같습니다.
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
이중 연결 리스트를 앞으로부터 순회
헤드 노드에서 순회하고 "NULL"을 찾을 때까지 다음 노드를 반복합니다. 각 노드를 순회하는 동안 노드의 값을 인쇄할 수 있습니다. 다음은 전면(전방향)에서 횡단하는 단계입니다.
단계 1) 현재 헤드 노드에 포인터나 변수를 할당합니다.
단계 2) "NULL"이 나올 때까지 헤드의 다음 노드를 반복합니다.
단계 3) 각 반복마다 노드의 데이터를 인쇄합니다.
단계 4) 헤드 노드를 반환합니다.
이중 연결 목록을 앞에서 순회하는 의사 코드는 다음과 같습니다.
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
여기서 반환은 필수는 아닙니다. 하지만 작업 후 헤드 노드를 반환하는 것이 좋은 관행입니다.
이중 연결 리스트를 뒤에서부터 순회
이 작업은 전면에서 횡단하는 것과 반대입니다. 접근 방식은 약간 다르지만 동일합니다. 끝 노드까지 횡단한 다음 끝 노드에서 전면 노드까지 횡단해야 합니다.
이중 연결 리스트를 뒤에서 순회하는 단계는 다음과 같습니다.
단계 1) 꼬리 노드에 도달할 때까지 횡단합니다.
단계 2) 꼬리 노드에서 이전 노드가 "NULL"이 될 때까지 순회합니다. "prev"(이전 포인터)는 헤드 노드에 대해 null입니다.
단계 3) 각 반복마다 노드 데이터를 인쇄합니다.
뒤에서 탐색하기 위한 의사 코드는 다음과 같습니다.
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
단일 연결 목록과 이중 연결 목록의 차이점
단일 연결 목록과 이중 연결 목록의 주요 차이점은 링크 수입니다.
단일 연결 목록의 노드와 이중 연결 목록의 노드 구조 간의 차이점은 다음과 같습니다.
| 분야 | 단일 연결 목록 | 이중 연결 목록 |
|---|---|---|
| Structure | 단일 연결 목록 하나의 데이터 필드와 다음 노드에 대한 하나의 링크가 있습니다. | 이중 연결 목록에는 하나의 데이터 필드와 두 개의 링크가 있습니다. 하나는 이전 노드용이고 다른 하나는 다음 노드용입니다. |
| 순회 | 머리에서 꼬리까지만 횡단할 수 있습니다. | 앞뒤로 모두 이동할 수 있습니다. |
| 메모리 | 메모리를 덜 차지합니다. | 단일 연결 리스트보다 더 많은 메모리를 차지합니다. |
| 접근 용이성 | 단일 연결 목록은 다음 노드에 대한 링크를 하나만 사용하므로 효율성이 떨어집니다. 이전 노드에 대한 링크가 없습니다. | 이중 연결 목록은 단일 연결 목록보다 효율적입니다. |
이중 연결리스트 C++
#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
struct node *prev;
};
void insertFront(node* &listHead, int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
if(listHead!=NULL)
{
listHead->prev = newNode;
newNode->next = listHead;
}
listHead = newNode;
cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node * &listHead, int value){
if(listHead==NULL)
{
insertFront(listHead,value);
}
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
node *head = listHead;
while(head->next!=NULL){
head = head->next;
}
head->next = newNode;
newNode->prev = head;
cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node * &listHead, int searchValue,int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
node *head = listHead;
while(head->next!=NULL && head->data!=searchValue){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
newNode->prev = head;
if(newNode->next !=NULL){
newNode->next->prev = newNode;
}
cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node * &listHead, int searchValue,int value){
node* newNode = new node();
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
node *head = listHead;
while(head->next!=NULL && head->next->data!=searchValue){
head = head->next;
}
newNode->next = head->next;
head->next = newNode;
newNode->prev = head;
if(newNode->next !=NULL){
newNode->next->prev = newNode;
}
cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
node* head = new node();
head = listHead;
cout<<"Traversal from head:\t";
while(head!=NULL){
cout<<head->data<<"\t ";
head = head->next;
}
cout<<endl;
}
void traverseFromEnd(node *listHead){
node* head = new node();
head = listHead;
cout<<"Traversal from head:\t";
while(head->next!=NULL){
head = head->next;
}
node *tail = head;
while(tail!=NULL){
cout<<tail->data<<"\t";
tail = tail->prev;
}
cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
node* head = new node();
head = (*listHead);
while(head->next!=NULL && head->data!=searchItem){
head = head->next;
}
if(*listHead == NULL || head == NULL) return;
if((*listHead)->data == head->data){
*listHead = head->next;
}
if(head->next != NULL){
head->next->prev = head->prev;
}
if(head->prev != NULL){
head->prev->next = head->next;
}
free(head);
cout<<"Deleted Node\t"<<searchItem<<endl;
return;
}
int main(){
node *head = NULL;
insertFront(head,5);
insertFront(head,6);
insertFront(head,7);
insertEnd(head,9);
insertEnd(head,10);
insertAfter(head,5,11);
insertBefore(head,5,20);
traverseFromFront(head);
traverseFromEnd(head);
searchAndDelete(&head,7);
traverseFromFront(head);
traverseFromEnd(head);
}
산출
Added 5 at the front Added 6 at the front Added 7 at the front Aded 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversal from head: 7 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
이중 연결리스트 Python
class node:
def __init__(self,data = None, prev=None, next = None):
self.data = data
self.next = next
self.prev = prev
class DoublyLinkedList:
def __init__(self):
self.head = None
def insertFront(self, val):
newNode = node(data=val)
newNode.next = self.head
if self.head is not None:
self.head.prev = newNode
self.head = newNode
print("Added {} at the front".format(val))
def insertEnd(self,val):
newNode = node(data=val)
if self.head is None:
self.insertFront(val)
temp = self.head
while temp.next is not None:
temp = temp.next
temp.next = newNode
newNode.prev = temp
print("Added {} at the end".format(val))
def traverseFromFront(self):
temp = self.head
print("Traversing from head:\t",end="")
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()
def traverseFromEnd(self):
temp = self.head
print("Traversing from Tail:\t",end="")
while temp.next is not None:
temp = temp.next
tail = temp
while tail is not None:
print("{}\t".format(tail.data),end="")
tail = tail.prev
print()
def insertAfter(self,searchItem, value):
newNode = node(data=value)
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
newNode.prev = temp
if newNode.next is not None:
newNode.next.prev = newNode
print("Inserted {} after node {}".format(value,searchItem))
def insertBefore(self,searchItem, value):
newNode = node(data=value)
temp = self.head
while temp.next is not None and temp.next.data is not searchItem:
temp = temp.next
newNode.next = temp.next
temp.next = newNode
newNode.prev = temp
if newNode.next is not None:
newNode.next.prev = newNode
print("Inserted {} before node {}".format(value,searchItem))
def searchAndDelete(self,searchItem):
temp = self.head
while temp.next is not None and temp.data is not searchItem:
temp = temp.next
if self.head is None or temp is None:
return
if self.head.data is temp.data:
self.head = temp.next
if temp.next is not None:
temp.next.prev = temp.prev
if temp.prev is not None:
temp.prev.next = temp.next
print("Deleted Node\t{}".format(searchItem))
return
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
산출
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Added 10 at the end Inserted 11 after node 5 Inserted 20 before node 5 Traversing from head: 7 6 20 5 11 9 10 Traversing from Tail: 10 9 11 5 20 6 7 Deleted Node 7 Traversing from head: 6 20 5 11 9 10 Traversing from Tail: 10 9 11 5 20 6
이중 연결 리스트의 복잡성
일반적으로 시간 복잡도는 세 가지 유형으로 나뉜다.
그들은 :
- 최상의 사례
- 평균 케이스
- 최악의 경우
이중 연결 리스트의 최상의 경우 시간 복잡도:
- head 또는 tail에 삽입하면 O(1)이 듭니다. 연결 리스트 내부를 탐색할 필요가 없기 때문입니다. head와 tail 포인터를 통해 O(1) 시간 복잡도로 head와 tail 노드에 접근할 수 있습니다.
- 머리 또는 꼬리 부분을 삭제하면 O(1)의 비용이 발생합니다.
- 노드 검색은 O(1)의 시간 복잡도를 갖습니다. 왜냐하면 대상 노드가 헤드 노드가 될 수 있기 때문입니다.
이중 연결 리스트의 평균적 경우의 시간 복잡도:
- 머리 또는 꼬리에 삽입하면 비용 O(1)의 시간 복잡도가 발생합니다.
- 머리 또는 꼬리 부분에서 삭제하면 비용 O(1)의 시간 복잡도가 발생합니다.
- 노드를 검색하는 데는 O(n)의 시간 복잡도가 있습니다. 검색 항목은 연결 리스트 사이의 어디에나 있을 수 있기 때문입니다. 여기서 "n"은 연결 리스트에 있는 전체 노드입니다.
이중 연결 리스트의 최악의 경우 시간 복잡도는 평균적인 경우와 동일합니다.
이중 연결 리스트의 메모리 복잡도
메모리 복잡도는 O(n)이며, 여기서 "n"은 노드의 총 개수입니다. 연결 리스트를 구현하는 동안 사용한 메모리를 해제해야 합니다. 그렇지 않으면 더 큰 연결 리스트의 경우 메모리 누수가 발생합니다.
요약
- 연결된 목록은 일종의 선형 데이터 구조로, 선형 방식으로 표현되는 데이터 모음입니다.
- 이중 연결 리스트(Double Linked List)는 한 노드가 이전 노드와 다음 노드 모두와 연결되어 있는 일종의 연결 리스트입니다.
- 이중 연결 리스트에는 노드 추가, 노드 삭제, 노드 뒤나 앞에 노드 삽입, 연결 리스트를 머리부터 꼬리까지 탐색하는 등의 모든 작업이 포함되어 있습니다.
- 이중 연결 목록에는 하나의 데이터 필드와 두 개의 링크가 있습니다. 하나는 이전 노드용이고 다른 하나는 다음 노드용입니다.
- 이중 연결 리스트의 복잡성 최상의 경우, 평균적 경우
- 그리고 최악의 경우.
