Двойной связанный список определяется как когда в узле есть 2 указателя, в котором один указатель ссылается на адрес следующего элемента данных.

Терминология, используемая в двусвязном списке,

  1. head: ссылается на адрес первого элемента данных.
  2. последний:относится к адресу последнего элемента данных.
  3. prev:сохраняет адрес предыдущего элемента данных.
  4. следующий. Сохраняет адрес следующего элемента данных.
  5. элемент данных. Сохраняет данные в памяти.
  6. узел. Сочетание предыдущего, следующего и элемента данных.

В отличие от односвязного списка, двусвязный список может перемещаться как вперед, так и назад.

Представление двусвязного списка:

Вставка:

Он вставляет узел в конец двусвязного списка. Адрес последнего и последнего следующего изменяются на адрес нового узла.

Удаление:

Он удаляет последний узел из двусвязного списка. Он меняет значения последнего и предпоследнего узла next .

Поиск:

Он пытается найти элемент из двусвязного списка. используя prev и next, поиск перемещается вперед и назад.

Обход:

Он отображает все элементы, хранящиеся в двойном связанном списке. он может двигаться либо спереди назад, либо сзади вперед.

Теперь давайте посмотрим на программы из списка Double Linked:

  1. C
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node* prev;
struct Node *next;
};
struct Node* head=NULL;
struct Node* last=NULL;
void Inertion();
void Deletion();
void Search();
void Traversal();
int main()
{
int i;
while(1){
printf("1.Insertion\n2.Deletion\n3.Search\n4.Traversal\n5.Exit\nEnter your choice:");
scanf("%d",&i);
switch(i){
case 1:Insertion();
break;
case 2:Deletion();
break;
case 3:Search();
break;
case 4:Traversal();
break;
case 5:exit(0);
}
}
return 0;
}
void Insertion()
{
struct Node* n1;
n1=(struct Node *)malloc(sizeof(struct Node));
printf("Enter the data item:");
scanf("%d",&n1->data);
n1->prev=NULL;
n1->next=NULL;
if(head==NULL){
head=n1;
last=n1;
}
else{
last->next=n1;
n1->prev=last;
last=n1;
}
}
void Deletion()
{
if(head==NULL)
printf("NO elements to delete");
else{
printf("%d is deleted");
last=last->prev;
last->next=NULL;
}
}
void Search()
{
int key;
struct Node *temp;
if(head==NULL)
printf("No elements to search");
else{
temp=head;
printf("enter the key:");
scanf("%d",&key);
while(temp!=NULL)
{
if(temp->data==key)
break;
temp=temp->next;
}
if(temp==NULL)
printf("Key not found");
else
printf("Search success");
}
}
void Traversal(){
struct Node *temp;
if(head==NULL)
printf("No elements to display");
else{
temp=head;
while(temp!=NULL)
{
printf("%d\t",temp->data);
temp=temp->next;
}
}
}
view raw DoubleLinkedList.c hosted with ❤ by GitHub

2.Java

import java.lang.*;
import java.util.Scanner;
class Node{
int data;
Node prev;
Node next;
}
class DoubleLinkedList{
static Node head;
static Node last;
static int i;
void Insertion(int data)
{
Node n=new Node();
n.data=data;
n.prev=null;
n.next=null;
if(head==null)
{
head=last=n;
}
else
{
n.prev=last;
last.next=n;
last=n;
}
}
void Deletion()
{
if(head==null)
System.out.println("No elements to delete");
else if(head==last)
{
System.out.println("The deleted element is "+head.data);
head=null;
last=null;
}
else
{
System.out.println("The deleted element is "+last.data);
last=last.prev;
last.next=null;
}
}
void Search(int key)
{
Node temp;
if(head==null)
System.out.println("No elements to search");
else
{
temp=head;
while(temp!=null)
{
if(temp.data==key)
break;
temp=temp.next;
}
if(temp==null)
System.out.println("Key not found");
else
System.out.println("Search Success");
}
}
void Traversal()
{
if(head==null)
System.out.println("no elements to traversal");
else
{
Node temp=head;
while(temp!=null)
{
System.out.print(temp.data+" ");
temp=temp.next;
}
}
}
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
DoubleLinkedList n1=new DoubleLinkedList();
while(true)
{
System.out.println("1.Insertion");
System.out.println("2.Deletion");
System.out.println("3.Search");
System.out.println("4.Traversal");
System.out.println("5.Exit");
System.out.println("Enter your choice:");
i=sc.nextInt();
switch(i)
{
case 1:
System.out.println("Enter theb element to insert:");
n1.Insertion(sc.nextInt());
break;
case 2:
n1.Deletion();
break;
case 3:
System.out.println("Enter thye key to search:");
n1.Search(sc.nextInt());
break;
case 4:
n1.Traversal();
break;
case 5:
System.exit(0);
}
}
}
}
view raw DoubleLinkedList.java hosted with ❤ by GitHub

На этом мы закончим концепцию двойного связанного списка.

Моя следующая история будет о циклическом связанном списке.

Спасибо.