Bidirectional Link List and Its Creation

 

At present, the linked list we have learned, whether dynamic or static, contains only one pointer (cursor) in each node of the list, and all points to the direct successor node in a unified way. Usually, this kind of linked list is called one-way linked list (or single linked list).

Although using single linked list can solve the storage problem of "one-to-one" data with logical relationship 100%, it is not the most efficient storage structure when solving some special problems. For example, if the algorithm needs to find a large number of forward nodes of a given node, the use of single-linked list is undoubtedly catastrophic, because single-linked list is more suitable for "from before to after" search, and "from behind to forward" search is not its strong point.

In order to solve similar problems efficiently, this section will study the two-way linked list (referred to as double linked list).

Understand the bi-directional list by name, that is, the list is "bi-directional", as shown in Figure 1.

 

Fig. 1 Diagram of bi-directional linked list structure

 

Two-way refers to the logical relationship between nodes is bidirectional, but usually only one header pointer is set, unless the actual situation requires.

As you can see from Figure 1, each node in the two-way linked list contains the following three parts of information (as shown in Figure 2):

  1. Pointer field: the direct precursor node used to point to the current node;
  2. Data Domain: Used to store data elements.
  3. Pointer field: used to point to the immediate successor node of the current node;
Figure 2 Node composition of the bidirectional linked list


Therefore, the node structure of double linked list is implemented in C language as follows:

typedef struct line{
struct line * prior; //Directing towards direct forward trend
int data;
struct line * next; //Direct succession
}line;

Creation of Bidirectional Link List

Compared with single linked list, double linked list is only one more pointer field for each node to point to the direct precursor. Therefore, we can easily create double linked list on the basis of single linked list.

It should be noted that, unlike single-linked lists, in the process of creating double-linked lists, for each new node, two links are established with its precursor nodes, namely:

  • The prior pointer of the new node is pointed to the direct precursor node.
  • The next pointer of the direct precursor node is pointed to the new node.

The C language implementation code for creating a two-way linked list is given here.

line* initLine(line * head){
    head=(line*)malloc(sizeof(line));//Create the first node of the list (the head node)
    head->prior=NULL;
    head->next=NULL;
    head->data=1;
    line * list=head;
    for (int i=2; i<=3; i++) {
        //Create and initialize a new node
        line * body=(line*)malloc(sizeof(line));
        body->prior=NULL;
        body->next=NULL;
        body->data=i;
      
        list->next=body;//The next pointer of the direct forward node points to the new node
        body->prior=list;//New Node Points to Direct Forward Trend Node
        list=list->next;
    }
    return head;
}

Diagram:

We can try to output the double linked list created in main function. The C language code is as follows:

#include <stdio.h>
#include <stdlib.h>
//Node structure
typedef struct line{
struct line * prior;
int data;
struct line * next;
}line;
//Creation function of double linked list
line* initLine(line * head);
//Functions of Output Double-linked List
void display(line * head);

int main() {
//Create a header pointer
line * head=NULL;
//Call the linked list creation function
head=initLine(head);
//Output Created Link List
display(head);
//Display the advantages of double linked lists
printf("The direct precursor of the fourth node in the list is:%d",head->next->next->next->prior->data);
return 0;
}
line* initLine(line * head){
//Create a header node with the header pointer of the linked list as head
head=(line*)malloc(sizeof(line));
//Initialization of nodes
head->prior=NULL;
head->next=NULL;
head->data=1;
//Declare a pointer to the primary node to facilitate the late addition of newly created nodes to the list
line * list=head;
for (int i=2; i<=5; i++) {
//Create new nodes and initialize them
line * body=(line*)malloc(sizeof(line));
body->prior=NULL;
body->next=NULL;
body->data=i;

//New node establishes relationship with the last node in the list
list->next=body;
body->prior=list;
//List always points to the last node in the list
list=list->next;
}
//Returns the newly created linked list
return head;
}
void display(line * head){
line * temp=head;
while (temp) {
//If the node has no successor node, it is the last node in the list.
if (temp->next==NULL) {
printf("%d\n",temp->data);
}else{
printf("%d <-> ",temp->data);
}
temp=temp->next;
}
}

 

 

 

 

 

 

 

 

 

Tags: C

Posted on Sat, 07 Sep 2019 04:09:37 -0700 by altumdesign