Data structure of double linked list

What is the Doubly Linked List?

The Doubly Linked List is a variant of the Linked List, in which browsing through the buttons can be done in two ways: easy forward and backward. when compared with Single Link List. Here are some important concepts to keep in mind about the Double Link List.

Link : each link of a linked List can store a data and is called an element.

Next : each link of a linked list can contain a link to the next link and is called Next.

Prev : each link of a linked list may contain a link to previous links and is called Prev.

First and Last : a List of links containing links that link to the first link called First and to the last link called Last.

Performing List of double links

As shown above, you need to remember:

The list of double links contains a link element and is called First and Last.

Each link has a data field and a link field called Next.

Each link is linked to the next element by using Next Link.

Each link is linked to the previous element by using Prev Link.

Last Link brings a link pointing to NULL to mark the end of the Link List.

Basic activities on the Double Link List

Insert operation : add an element to the top position of the Linked List.

Delete operation : delete an element at the beginning of the Linked List.

Inserting operation at the end : add an element to the end position of the Linked List.

Activity to delete the last element: delete an element at the end of the Linked List.

The following insert operation : add an element after an element of the Linked List.

Delete operation (by key) : Delete an element from the Linked List by using the provided key.

Display the list forward : display the entire Link list in the forward direction.

Display the list to the back : display the entire Link list in the backward direction.

Insert operation in the double linked list

The following is an algorithm that illustrates the insert operation at the beginning of a double linked list.

 //Chèn link tại vị trí đầu tiên void insertFirst ( int key , int data ) { //tạo một link struct node * link = ( struct node *) malloc ( sizeof ( struct node )); link -> key = key ; link -> data = data ; if ( isEmpty ()) { //Biến nó thành last link last = link ; } else { //Cập nhật prev link đầu tiên head -> prev = link ; } //Trỏ nó tới first link cũ link -> next = head ; //Trỏ first tới first link mới head = link ; } 

To find out the detailed code of the double linked list in C language, please click on the chapter: Program of double link list in C.

According to Tutorialspoint

Previous article: Linked list data structure (Linked List)

Next article: Loop List List (Circular Linked List)