데이터 구조-이중 연결 목록

이중 연결 목록은 단일 연결 목록에 비해 앞뒤로 쉽게 탐색 할 수있는 연결 목록의 변형입니다. 다음은 이중 연결 목록의 개념을 이해하는 데 중요한 용어입니다.

Link − 링크드리스트의 각 링크는 요소라는 데이터를 저장할 수 있습니다.
Next − 링크 된 목록의 각 링크는 다음이라는 다음 링크에 대한 링크를 포함합니다.
Prev − 링크 된 목록의 각 링크는 이전 링크 인 Prev에 대한 링크를 포함합니다.
LinkedList − Linked List에는 First라는 첫 번째 링크와 Last라는 마지막 링크에 대한 연결 링크가 포함되어 있습니다.

이중 연결 목록 표현

위의 그림에 따라 고려해야 할 중요한 사항은 다음과 같습니다.

이중 연결 목록에는 첫 번째와 마지막이라는 링크 요소가 있습니다.
각 링크에는 데이터 필드와 next 및 prev라는 두 개의 링크 필드가 있습니다.
각 링크는 다음 링크를 사용하여 다음 링크와 연결됩니다.
각 링크는 이전 링크를 사용하여 이전 링크와 연결됩니다.
마지막 링크는 목록의 끝을 표시하기 위해 링크를 null로 전달합니다.

기본 작동

다음은 목록에서 지원하는 기본 작업입니다.

Insertion − 목록 시작 부분에 요소를 추가합니다.
Deletion − 목록의 시작 부분에있는 요소를 삭제합니다.
Insert Last − 목록 끝에 요소를 추가합니다.
Delete Last − 목록 끝에서 요소를 삭제합니다.
Insert After − 목록의 항목 뒤에 요소를 추가합니다.
Delete − 키를 사용하여 목록에서 요소를 삭제합니다.
Display forward − 전체 목록을 순방향으로 표시합니다.
Display backward − 전체 목록을 역순으로 표시합니다.

삽입 작업

다음 코드는 이중 연결 목록의 시작 부분에 삽입 작업을 보여줍니다.

예

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

삭제 작업

다음 코드는 이중 연결 목록의 시작 부분에서 삭제 작업을 보여줍니다.

예

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

작업 종료시 삽입

다음 코드는 이중 연결 목록의 마지막 위치에서 삽입 작업을 보여줍니다.

예

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

C 프로그래밍 언어로 구현 된 내용을 보려면 여기 를 클릭하십시오 .