이중 연결 목록: C++, Python (Code 예)

⚡ 스마트 요약

이중 연결 리스트는 각 노드에 데이터와 함께 이전 노드와 다음 노드를 가리키는 포인터 두 개가 저장되는 선형 데이터 구조입니다. 따라서 앞뒤로 효율적으로 이동할 수 있습니다.

🧩 노드 구조: 이중 연결 리스트의 각 노드는 데이터 필드를 보유합니다. 이전 이전 노드를 가리키는 포인터, 그리고 다음 것 다음 노드를 가리키는 포인터입니다.
🔁 양방향 탐색: 추가적인 이전 포인터 덕분에 알고리즘은 헤드에서 테일로, 테일에서 헤드로 탐색할 수 있는데, 이는 단일 연결 리스트로는 불가능한 기능입니다.
➕ 삽입 Operations : 노드는 상수 시간 또는 선형 시간 내에 시작 부분, 끝 부분, 대상 노드 뒤 또는 대상 노드 앞에 추가할 수 있습니다.
➖ 삭제 Operations : 헤드, 테일 또는 일치하는 노드를 제거하면 이웃 노드의 이전 및 다음 포인터가 모두 업데이트되고 해제된 메모리가 해제됩니다.
💻 C++ Python Code: 완전한 구현을 통해 삽입, 삭제, 검색 및 순회 루틴을 실행 가능한 출력과 함께 보여줍니다.
📊 복잡성: 헤드 또는 테일에서의 삽입 또는 삭제 비용은 O(1)이고 검색 비용은 평균적으로 O(n)이며 전체 공간 복잡도는 O(n)입니다.
🏭 어플리케이션 : 데크(Deque), LRU 캐시, 브라우저 기록, 실행 취소 및 다시 실행 스택, 음악 플레이어 재생 목록은 이중 연결 리스트에 의존합니다.

이중 연결 리스트란 무엇인가요?

이중 연결 리스트에서 각 노드는 이전 노드와 다음 노드를 가리키는 링크를 가지고 있습니다. 각 노드는 세 개의 요소로 구성되는데, 하나는 데이터를 저장하고 나머지 두 개는 이전 노드와 다음 노드를 가리키는 포인터입니다. 이 두 포인터를 이용하여 특정 노드에서 앞뒤로 이동할 수 있습니다.

다음은 이중 연결 리스트의 기본 구조입니다.

이중 연결 목록의 구조

모든 연결 리스트에는 헤드 노드와 테일 노드가 있습니다. 헤드 노드는 아무런 연결 관계를 갖지 않습니다. 이전 (이전 포인터) 노드이고, 꼬리 노드에는 아무것도 없습니다. 다음 것 마디.

이중 연결 리스트에서 중요한 용어 몇 가지를 소개합니다.

이전 : 각 노드는 이전 노드에 연결됩니다. 포인터나 링크로 사용됩니다.
다음 : 각 노드는 다음 노드에 연결됩니다. 포인터나 링크로 사용됩니다.
날짜 : 이것은 노드에 데이터를 저장하는 데 사용됩니다. 데이터는 다른 정보를 담을 수 있습니다. 데이터 구조 그 안에 문자열, 딕셔너리, 세트, 해시맵 등의 구조체를 데이터 필드에 저장할 수 있습니다.

다음은 이중 연결 리스트에서 단일 노드의 기본 구조입니다.

이중 연결 목록의 노드 구조

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:
    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:
    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:
    List = List.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
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

이중 연결 리스트에서 노드를 검색하고 삭제하기

이 연산은 특정 노드 값을 검색하여 해당 노드를 삭제합니다. 연결 리스트는 선형 데이터 구조이므로 선형 검색이 필요합니다. 삭제 후에는 메모리를 해제해야 합니다.

이중 연결 리스트에서 노드를 검색하고 삭제하는 단계는 다음과 같습니다.

단계 1) 연결 리스트의 맨 앞 노드부터 시작하여 검색 항목과 값이 같아지는 노드까지 순회합니다.

단계 2) 변수를 할당합니다 노드 삭제 일치하는 노드로 이동합니다.

단계 3) 이전 노드를 연결합니다 노드 삭제 다음 노드로 이동하고 다음 노드의 값을 설정합니다. 이전 이전 노드를 가리키는 포인터입니다.

단계 4) 기억을 해방시키세요 노드 삭제.

다음은 연결 리스트에서 노드를 검색하고 삭제하는 의사 코드입니다.

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

검색 및 삭제 작업

이중 연결 리스트를 순방향으로 탐색합니다.

헤드 노드에서 시작하여 다음 노드를 순차적으로 탐색하며, NULL 값을 찾을 때까지 계속합니다. 각 노드를 탐색하는 동안 해당 값을 출력할 수 있습니다. 순방향으로 탐색하는 단계는 다음과 같습니다.

단계 1) 현재 헤드 노드에 포인터나 변수를 할당합니다.

단계 2) NULL이 나올 때까지 헤드의 다음 노드로 반복합니다.

단계 3) 각 반복마다 노드 데이터를 출력합니다.

단계 4) 헤드 노드를 반환합니다.

다음은 이중 연결 리스트를 앞에서부터 순회하는 의사 코드입니다.

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

반환은 필수 사항은 아닙니다. 하지만 작업 후 헤드 노드를 반환하는 것이 좋습니다.

이중 연결 리스트를 역방향으로 순회합니다.

이 작업은 앞에서부터 순회하는 것의 역순입니다. 접근 방식은 동일하지만 한 가지 작은 차이점이 있습니다. 먼저 끝 노드에 도달한 다음, 역방향으로 이동하여 시작 노드로 돌아갑니다. 이전 바늘.

다음은 이중 연결 리스트를 뒤에서부터 순회하는 단계입니다.

단계 1) 꼬리 노드에 도달할 때까지 이동합니다.

단계 2) 꼬리 노드에서 시작하여 다음을 사용하여 순회합니다. 이전 이전 노드가 NULL이 될 때까지. 이전 헤드 노드의 포인터가 null입니다.

단계 3) 각 반복마다 노드 데이터를 출력합니다.

다음은 뒤에서부터 순회하는 의사 코드입니다.

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

단일 연결 리스트와 이중 연결 리스트의 차이점

단일 연결 리스트와 이중 연결 리스트의 주요 차이점은 각 노드가 보유하는 링크의 수입니다.

단일 연결 리스트와 이중 연결 리스트의 노드 차이점은 다음과 같습니다.

분야	단일 연결 목록	이중 연결 목록
Structure	단일 연결 목록 하나의 데이터 필드와 다음 노드에 대한 하나의 링크가 있습니다.	이중 연결 목록에는 하나의 데이터 필드와 두 개의 링크가 있습니다. 하나는 이전 노드용이고 다른 하나는 다음 노드용입니다.
순회	머리에서 꼬리까지만 횡단할 수 있습니다.	앞뒤로 모두 이동할 수 있습니다.
메모리	메모리를 덜 차지합니다.	단일 연결 리스트보다 더 많은 메모리를 차지합니다.
접근 용이성	단일 연결 리스트는 다음 노드로 연결되는 링크가 하나뿐이므로 효율성이 떨어집니다. 이전 노드로 연결되는 링크는 없습니다.	양방향 접근에 있어서 이중 연결 리스트는 단일 연결 리스트보다 더 효율적입니다.

이중 연결리스트 C++

아래는 전체 내용입니다. 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);
    return;
  }
  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 = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\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 = (*listHead);
  while(head != 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;
}
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
Added 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 tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

이중 연결리스트 Python

아래는 전체 내용입니다. 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.head = newNode
      print("Added {} at the end".format(val))
      return
    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 is not None:
      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 != 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 != 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 is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == 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))
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

이중 연결 리스트의 복잡성

시간 복잡도는 일반적으로 최상 사례, 평균 사례, 최악 사례의 세 가지 유형으로 나뉩니다.

이중 연결 리스트의 최상의 경우 시간 복잡도:

헤드나 테일에 삽입하는 데는 연결 리스트 내부를 순회할 필요가 없으므로 O(1)의 비용이 듭니다. 헤드 및 테일 포인터를 사용하면 헤드 및 테일 노드에 직접 접근할 수 있습니다.
머리나 꼬리에서 삭제하는 데 드는 비용은 O(1)입니다.
대상 노드가 헤드 노드인 경우 노드 검색 비용은 O(1)입니다.

이중 연결 리스트의 평균적 경우의 시간 복잡도:

머리나 꼬리에 삽입하는 데 드는 비용은 O(1)입니다.
머리나 꼬리에서 삭제하는 데 드는 비용은 O(1)입니다.
노드를 검색하는 데 O(n)의 비용이 듭니다. 왜냐하면 목표 노드는 리스트의 어디에든 있을 수 있기 때문입니다. 여기서는, n 노드의 총 개수입니다.

이중 연결 리스트의 최악의 경우 시간 복잡도는 평균적인 경우와 동일합니다.

이중 연결 리스트의 메모리 복잡도

메모리 복잡도는 O(n)입니다. n 는 전체 노드 수입니다. 연결 리스트를 구현할 때는 메모리를 반드시 해제해야 합니다. 그렇지 않으면, 크기가 큰 연결 리스트에서 메모리 누수가 발생할 수 있습니다.

이중 연결 리스트의 응용

양방향 순회가 많은 일반적인 연산을 단순화하기 때문에 이중 연결 리스트는 여러 실제 데이터 구조에서 핵심적인 역할을 합니다.

LRU 캐시: 최근 사용되지 않은 캐시는 O(1) 이동-앞으로 이동 및 제거를 위해 해시맵이 있는 이중 연결 리스트를 사용합니다.
브라우저 기록 : 뒤로 가기 및 앞으로 가기 탐색은 연결 리스트를 양방향으로 이동합니다.
실행 취소 및 다시 실행 스택: 에디터 및 IDE track개의 문서 버전과 이전 및 다음 포인터가 있습니다.
데크: Double-끝 큐는 O(1) 시간 내에 양쪽 끝에서 푸시 및 팝합니다.
음악 재생 목록: 이전과 다음 track 버튼은 앞뒤 포인터에 의존합니다.

자주 묻는 질문

이중 연결 리스트는 딥러닝 배치 파이프라인과 벡터 스토어 프런트엔드에서 사용되는 LRU 캐시를 지원하며, AI 시스템이 최근 액세스한 텐서를 빠른 재사용을 위해 O(1) 시간 내에 헤드로 이동할 수 있도록 합니다.

네. GitHub Copilot과 GPT는 C 언어로 완전한 이중 연결 리스트를 생성할 수 있습니다. C++, Java, Python또는 Rust를 사용하여 삽입, 삭제, 검색 및 역방향 탐색 메서드를 포함한 다양한 기능을 제공하며, 단위 테스트도 지원합니다.

단일 연결 리스트는 다음 노드를 가리키는 포인터가 하나 있으며 한 방향으로만 순회합니다. 이중 연결 리스트는 이전 노드와 다음 노드를 가리키는 포인터가 모두 있으며 앞뒤로 순회하지만 더 많은 메모리를 사용합니다.

일반적인 응용 분야로는 LRU 캐시, 브라우저의 뒤로 가기 및 앞으로 가기 기록, 편집기의 실행 취소 및 다시 실행 스택, 덱 구현, 재생 목록 탐색, 운영 체제의 스레드 스케줄링 등이 있습니다.

헤드 또는 테일에서의 삽입 또는 삭제는 O(1)입니다. 임의 위치에서의 검색, 삽입 또는 삭제는 O(n)입니다. 모든 노드가 추가적인 prev 포인터를 저장하기 때문에 공간 복잡도는 O(n)입니다.

이중 연결 리스트는 양쪽 끝에서 O(1) 삽입 및 삭제를 제공하고 동적 메모리 할당을 제공합니다. 배열은 O(1) 임의 접근과 더 나은 캐시 지역성을 제공합니다. 작업 부하에 따라 선택하십시오.

리스트를 한 바퀴 돌면서 각 노드의 이전 포인터와 다음 포인터를 서로 바꿉니다. 루프가 끝나면 헤드 포인터를 이전의 꼬리 포인터로 업데이트합니다. 이 연산은 O(n) 시간 복잡도로 실행됩니다.

네. 원형 이중 연결 리스트는 꼬리 부분의 다음 포인터를 머리 부분에, 머리 부분의 이전 포인터를 꼬리 부분에 연결합니다. 이 구조는 라운드 로빈 스케줄링과 버퍼링에 사용됩니다.

이중 연결 목록: C++, Python (Code 예)

이중 연결 리스트란 무엇인가요?

Opera이중 연결 목록의 종류

이중 연결 리스트의 맨 앞에 삽입

이중 연결 리스트의 끝에 삽입

노드 뒤에 삽입

노드 앞에 삽입

이중 연결 리스트의 헤드를 삭제합니다.

이중 연결 리스트의 꼬리 부분을 삭제합니다.

이중 연결 리스트에서 노드를 검색하고 삭제하기

이중 연결 리스트를 순방향으로 탐색합니다.

이중 연결 리스트를 역방향으로 순회합니다.

단일 연결 리스트와 이중 연결 리스트의 차이점

이중 연결리스트 C++

산출

이중 연결리스트 Python

산출

이중 연결 리스트의 복잡성

이중 연결 리스트의 응용

자주 묻는 질문

이 게시물을 요약하면 다음과 같습니다.

뉴스레터 신청하기

이중 연결 리스트란 무엇인가요?

Opera이중 연결 목록의 종류

이중 연결 리스트의 맨 앞에 삽입

이중 연결 리스트의 끝에 삽입

노드 뒤에 삽입

노드 앞에 삽입

관련 기사

이중 연결 리스트의 헤드를 삭제합니다.

이중 연결 리스트의 꼬리 부분을 삭제합니다.

이중 연결 리스트에서 노드를 검색하고 삭제하기

이중 연결 리스트를 순방향으로 탐색합니다.

이중 연결 리스트를 역방향으로 순회합니다.

단일 연결 리스트와 이중 연결 리스트의 차이점

이중 연결리스트 C++

산출

이중 연결리스트 Python

산출

이중 연결 리스트의 복잡성

이중 연결 리스트의 응용

자주 묻는 질문

이 게시물을 요약하면 다음과 같습니다.

뉴스레터 신청하기