이중 연결 목록은 노드가 시퀀스의 이전 노드와 다음 노드에 대한 포인터를 포함하는 복잡한 유형의 연결 목록입니다. 따라서 이중 연결 리스트에서 노드는 노드 데이터, 순서대로 다음 노드에 대한 포인터(다음 포인터), 이전 노드에 대한 포인터(이전 포인터)의 세 부분으로 구성됩니다. 이중 연결 리스트의 샘플 노드가 그림에 표시되어 있습니다.
자바 정렬 배열 목록
데이터 부분에 1부터 3까지의 숫자가 있는 세 개의 노드를 포함하는 이중 연결 목록이 다음 이미지에 표시됩니다.
C에서 이중 연결 리스트의 노드 구조는 다음과 같이 주어질 수 있습니다.
struct node { struct node *prev; int data; struct node *next; } 그만큼 이전 첫 번째 노드의 일부와 다음 마지막 노드의 일부에는 항상 각 방향의 끝을 나타내는 null이 포함됩니다.
단일 연결 리스트에서는 각 노드에 다음 노드의 주소가 포함되어 있고 이전 노드에 대한 기록이 없기 때문에 한 방향으로만 이동할 수 있습니다. 그러나 이중 연결 리스트는 이러한 단일 연결 리스트의 한계를 극복합니다. 목록의 각 노드에는 이전 노드의 주소가 포함되어 있기 때문에 각 노드의 이전 부분에 저장된 이전 주소를 사용하여 이전 노드에 대한 모든 세부 정보도 찾을 수 있습니다.
이중 연결 리스트의 메모리 표현
이중 연결 목록의 메모리 표현은 다음 이미지에 표시됩니다. 일반적으로 이중 연결 목록은 모든 노드에 대해 더 많은 공간을 소비하므로 삽입 및 삭제와 같은 기본 작업이 더 광범위해집니다. 그러나 목록은 양방향(앞으로 및 뒤로)의 포인터를 유지하므로 목록의 요소를 쉽게 조작할 수 있습니다.
다음 이미지에서 목록의 첫 번째 요소인 13은 주소 1에 저장되어 있습니다. 헤드 포인터는 시작 주소 1을 가리킵니다. 이것이 목록에 추가되는 첫 번째 요소이므로 이전 목록의 포함 없는. 목록의 다음 노드는 주소 4에 있으므로 첫 번째 노드의 다음 포인터에는 4가 포함됩니다.
다음 부분에 null 또는 -1이 포함된 노드를 찾을 때까지 이러한 방식으로 목록을 탐색할 수 있습니다.
이중 연결 리스트의 작업
노드 생성
struct node { struct node *prev; int data; struct node *next; }; struct node *head; 이중 연결 리스트와 관련된 나머지 모든 작업은 다음 표에 설명되어 있습니다.
| SN | 작업 | 설명 |
|---|---|---|
| 1 | 처음에 삽입 | 처음에 연결된 목록에 노드를 추가합니다. |
| 2 | 끝에 삽입 | 연결리스트에 노드를 마지막에 추가합니다. |
| 삼 | 지정된 노드 뒤에 삽입 | 지정된 노드 뒤에 연결된 목록에 노드를 추가합니다. |
| 4 | 처음부터 삭제 | 목록의 시작 부분에서 노드 제거 |
| 5 | 마지막에 삭제 | 목록 끝에서 노드를 제거합니다. |
| 6 | 주어진 데이터를 가지고 있는 노드 삭제 | 주어진 데이터를 포함하는 노드 바로 뒤에 있는 노드를 제거합니다. |
| 7 | 수색 | 각 노드 데이터를 검색할 항목과 비교하고 항목이 발견되면 목록에서 항목의 위치를 반환하고 그렇지 않으면 null을 반환합니다. |
| 8 | 횡단 | 검색, 정렬, 표시 등과 같은 특정 작업을 수행하기 위해 목록의 각 노드를 한 번 이상 방문합니다. |
이중 연결 목록의 모든 작업을 구현하기 위한 C의 메뉴 기반 프로그램
#include #include struct node { struct node *prev; struct node *next; int data; }; struct node *head; void insertion_beginning(); void insertion_last(); void insertion_specified(); void deletion_beginning(); void deletion_last(); void deletion_specified(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('
*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: insertion_beginning(); break; case 2: insertion_last(); break; case 3: insertion_specified(); break; case 4: deletion_beginning(); break; case 5: deletion_last(); break; case 6: deletion_specified(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void insertion_beginning() { struct node *ptr; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter Item value'); scanf('%d',&item); if(head==NULL) { ptr->next = NULL; ptr->prev=NULL; ptr->data=item; head=ptr; } else { ptr->data=item; ptr->prev=NULL; ptr->next = head; head->prev=ptr; head=ptr; } printf('
Node inserted
'); } } void insertion_last() { struct node *ptr,*temp; int item; ptr = (struct node *) malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value'); scanf('%d',&item); ptr->data=item; if(head == NULL) { ptr->next = NULL; ptr->prev = NULL; head = ptr; } else { temp = head; while(temp->next!=NULL) { temp = temp->next; } temp->next = ptr; ptr ->prev=temp; ptr->next = NULL; } } printf('
node inserted
'); } void insertion_specified() { struct node *ptr,*temp; int item,loc,i; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { temp=head; printf('Enter the location'); scanf('%d',&loc); for(i=0;inext; if(temp == NULL) { printf('
There are less than %d elements', loc); return; } } printf('Enter value'); scanf('%d',&item); ptr->data = item; ptr->next = temp->next; ptr -> prev = temp; temp->next = ptr; temp->next->prev=ptr; printf('
node inserted
'); } } void deletion_beginning() { struct node *ptr; if(head == NULL) { printf('
UNDERFLOW'); } else if(head->next == NULL) { head = NULL; free(head); printf('
node deleted
'); } else { ptr = head; head = head -> next; head -> prev = NULL; free(ptr); printf('
node deleted
'); } } void deletion_last() { struct node *ptr; if(head == NULL) { printf('
UNDERFLOW'); } else if(head->next == NULL) { head = NULL; free(head); printf('
node deleted
'); } else { ptr = head; if(ptr->next != NULL) { ptr = ptr -> next; } ptr -> prev -> next = NULL; free(ptr); printf('
node deleted
'); } } void deletion_specified() { struct node *ptr, *temp; int val; printf('
Enter the data after which the node is to be deleted : '); scanf('%d', &val); ptr = head; while(ptr -> data != val) ptr = ptr -> next; if(ptr -> next == NULL) { printf('
Can't delete
'); } else if(ptr -> next -> next == NULL) { ptr ->next = NULL; } else { temp = ptr -> next; ptr -> next = temp -> next; temp -> next -> prev = ptr; free(temp); printf('
node deleted
'); } } void display() { struct node *ptr; printf('
printing values...
'); ptr = head; while(ptr != NULL) { printf('%d
',ptr->data); ptr=ptr->next; } } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('
item found at location %d ',i+1); flag=0; break; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('
Item not found
'); } } } 산출
*********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value12 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 1 Enter Item value1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 1234 123 12 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 2 Enter value89 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 3 Enter the location1 Enter value12345 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 1234 123 12345 12 89 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 4 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 5 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 123 12345 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 6 Enter the data after which the node is to be deleted : 123 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 8 printing values... 123 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 123 item found at location 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 6 Enter the data after which the node is to be deleted : 123 Can't delete *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete the node after the given data 7.Search 8.Show 9.Exit Enter your choice? 9 Exited..