Data structure and algorithm (a) linear table implementation

Data structure and algorithm (two) unidirectional circular linked list creation insert delete implementation

Data structure and algorithm (3) Implementation of bidirectional linked list and bidirectional cyclic linked list

Data structure and algorithm (4) linked list related interview questions

Data structure and algorithm (5) stack and queue operation and implementation

@TOC

To recap, we covered uni-directional lists and uni-directional lists in our previous blog, data Structures and Algorithms (2) Creation, insertion and deletion implementations of uni-directional lists. This blog focuses on the basic operation implementation of bidirectional lists and bidirectional circular lists.

Demo download of this blog:

Two-way linked list Demo
Bidirectional circular linked list Demo

1. Bidirectional linked lists

Why do we use a two-way list, and what are the advantages of a two-way list over a one-way list?

Singly linked lists relative to the order list, indeed in some scenarios to solve some important problems, such as the need to insert or delete a large number of elements, it does not need to move like a sequence table many elements, only need to modify the pointer points to, its time complexity is O (1) but this is a premise, that is all based on certain nodes, In purely delete and insert cases, but if we still don’t know where the nodes are, then singly linked lists have some problems

Let’s compare the delete operations of singly and doubly linked lists:

We want to delete a node. If we want to delete the second node a1, we only need to point the pointer of the primary node to the address of the third node:

A: Save the precursor of the current node while locating the node to be deleted
B: After the node is deleted, go back to the single-linked table header and locate the specified precursor

But no matter which method we choose, the total number of pointer moves will be 2n, and double-linked lists do a good job of this type of problem.

Let’s look at the process of deleting a node from a double-linked list:

We can count the number of operations they delete:

Although double-linked lists solve the pain point of reverse lookup in single-linked lists, but at the cost of adding a pointer field to each node, that is, using space to exchange.

Next, let’s look at the basic operation code implementation of bidirectional linked lists.

1.1 Node Definition

// Define the node
typedef struct KNode{
    KElementType data;  / / data
    struct KNode *prior; // Precursorsstruct KNode *next; // next pointer}Node;
Copy the code

Table 1.2 built

//5.1 Creating a bidirectional link
KStatus createLinkList(LinkList *L) {//*L points to the header
    *L = (LinkList)malloc(sizeof(KNode));
    if (*L= =NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    
    // Add data
    LinkList p = *L;
    for(int i=0; i < 10; i++){Create a temporary node
        LinkList temp = (LinkList)malloc(sizeof(KNode));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        
        // create a bidirectional linked list for the new node
        //① Temp is the successor of p
        p->next = temp;
        // < p style = "max-width: 100%; clear: both
        temp->prior = p;
        // the last node of p should be recorded to facilitate the next insertion
        p = p->next;
        
    }
    
    return OK;
}
Copy the code

1.3 Inserting nodes

Insert the element at position I as follows:

Create a new node q
Walk through the list to find the previous element P where you want to insert it
Place the precursor of the new element Q to p and the successor to p->next
Point the precursor of p->next to the new element Q
Refers the successors of p to the new element q

The implementation code of insert node is as follows:

//5.3 Insert elements into bidirectional lists
KStatus ListInsert(LinkList *L, int i, KElementType data){
    
    //1. Insert position is invalid 0 or negative
    if(i < 1) return ERROR;
    
    //2. Create a node
    LinkList temp = (LinkList)malloc(sizeof(KNode));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    
    //3. Point p to the header!
    LinkList p = *L;
    
    //4. Find the node directly inserted at position I
    for(int j = 1; j < i && p; j++) p = p->next;//5. If the insertion position exceeds the length of the list itself
    if(p == NULL) {return  ERROR;
    }
    
    //6. Check whether the insertion position is the end of the list;
    if (p->next == NULL) {
        
        p->next = temp;
        temp->prior = p;
    }else
    {
        //1️ PRIOR = temp on p->next
        p->next->prior = temp;
        //2️ retail temp->next points to original P ->next
        temp->next = p->next;
        //3️ retail -> Next update to newly created Temp
        p->next = temp;
        //4 newly created temp precursor = p ️
        temp->prior = p;
    }
    
    return  OK;
}
Copy the code

1.4 Deleting a Node

Delete the element in position I as follows:

Walk through the list to find the previous element P of the position you want to delete
Create a new node q and assign the element to be deleted to P
Point P -> Next to q-> Next, and precursors of Q -> Next to P
Release the q

The code for deleting nodes is as follows: (1) Delete nodes in the specified position of the bidirectional linked list

//5.4 Delete the node at the specified position in the bidirectional list
KStatus ListDelete(LinkList *L, int i, KElementType *e){
    
    int k = 1;
    LinkList p = (*L);
    
    //1. Check whether the bidirectional list is empty, if so, return ERROR;
    if (*L= =NULL) {
        return ERROR;
    }
    
  
    //2. Move the pointer p to the position before the deleted element
    while(k < i && p ! =NULL) {
        p = p->next;
        k++;
    }
    
    //3. Return ERROR if k> I or p == NULL
    if (k>i || p == NULL) {
        return  ERROR;
    }
    
    // create a temporary pointer delTemp to the node to be deleted, and assign the data of the node to *e
    LinkList delTemp = p->next;
    *e = delTemp->data;
    
    //5. P ->next equals the next node of the node to be deleted
    p->next = delTemp->next;
    
    //6. If the next node to be deleted is not null, then the precursor pointer to the next node to be deleted is assigned p;
    if(delTemp->next ! =NULL) {
        delTemp->next->prior = p;
    }
    
    // delete the delTemp node
    free(delTemp);
    
    return OK;
    
}
Copy the code

(2) Delete the elements specified in the bidirectional list

//5.5 Delete elements specified in the bidirectional list
KStatus LinkListDeletVAL(LinkList *L, int data){
    
    LinkList p = *L;
    
    //1. Loop through the bidirectional list
    while (p) {
       
        //2. Check whether the data field of the current node is equal to data. If so, delete the node
        if (p->data == data) {
            
            // Modify the successor pointer of the precursor node of the deleted node, refer to step 1️ on the figure
            p->prior->next = p->next;
            // Modify the precursor pointer of the successor node of the deleted node, refer to step 2️ on the figure
            if(p->next ! =NULL){
                p->next->prior = p->prior;
            }
            // Release node p
            free(p);
            // Exit the loop
            break;
        }
        
        // if this node is not found, continue to move pointer p
        p = p->next;
    }
    
    return OK;
    
}
Copy the code

1.5 traversal

//5.2 Prints the elements of the circular list
void display(LinkList L) {LinkList temp = L->next;
    
    if(temp == NULL){
        printf("Printed bidirectional linked list is empty! \n");
        return;
    }
    
    while (temp) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
    
}
Copy the code

1.6 find

//5.6.1 Finding elements in a bidirectional list
int selectElem(LinkList L.KElementType elem){
    
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == elem) {
            return i;
        }
        
        i++;
        p = p->next;
    }
    
    return  -1;
}
Copy the code

The 1.7 update

5.6.2 Update nodes in the bidirectional linked list
KStatus replaceLinkList(LinkList *L,int index,KElementType newElem){
    LinkList p = (*L)->next;
    
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    
    p->data = newElem;
    return OK;
}

Copy the code

1.8 Unit Tests

void test () {
    KStatus iStatus = 0;
      LinkList L;
      int temp,item,e;
      
      iStatus =  createLinkList(&L);
      printf("iStatus = %d\n",iStatus);
      printf("List created successfully, print list :\n");
      display(L);
      
      printf("Please enter the insertion location \n");
      scanf("%d %d",&temp,&item);
      iStatus = ListInsert(&L, temp, item);
      printf("Insert data, print linked list :\n");
      display(L);
      
      printf("Please enter the insertion location \n");
      scanf("%d %d",&temp,&item);
      iStatus = ListInsert(&L, temp, item);
      printf("Insert data, print linked list :\n");
      display(L);
      
      printf("Please enter the insertion location \n");
      scanf("%d %d",&temp,&item);
      iStatus = ListInsert(&L, temp, item);
      printf("Insert data, print linked list :\n");
      display(L);
      
      printf("Please enter deleted location \n");
      scanf("%d",&temp);
      iStatus = ListDelete(&L, temp, &e);
      printf("Delete element: delete element at %d,data = %d\n",temp,e);
      printf("After delete operation, bidirectional linked list :\n");
      display(L);
      
      printf("Please enter what you want to delete \n");
      scanf("%d",&temp);
      iStatus = LinkListDeletVAL(&L, temp);
      printf("Delete node where data field = %d, bidirectional linked list :\n",temp);
      display(L);

      printf("Please enter what you are looking for \n");
       scanf("%d",&temp);
      KElementType index = selectElem(L, temp);
      printf(%d\n :%d\n :%d\n,temp,index);

      printf("Please enter the node you want to update and the content \n");
      scanf("%d %d",&temp,&item);
      iStatus = replaceLinkList(&L, temp, item);
      printf("Bidirectional linked list after updating node data :\n");
      display(L);
}
Copy the code

Output result:

Hello, World! 0 1 2 3 4 5 6 7 8 9 Insert the data into the list: 66 0 1 2 3 4 5 6 7 8 9 Insert the data into the list 10 66 insert the data to print the list: 66 0 12 3 4 5 6 7 66 8 9 Please input the insertion position 12 77 Insert data, print the linked list: 66 0 12 3 4 5 6 7 66 8 77 9 Please input the deletion position 1 66 delete elements: 1, 2, 3, 4, 5, 6, 7, 66, 8, 77, 9 Delete the node whose data field is 66: 0, 1, 2, 3, 4, 5, 6, 7, 8, 77, 9 Please input what you want to find 77 node in the bidirectional linked list, the location is :10 Please input the node you want to update and the contentCopy the code

1.9 Complete Code

//
// main.c
// 005_DoubleLinkedList
//
// Created by bog on 2020/4/5
// Copyright © 2020 Apple. All rights reserved
//

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* Initial allocation of storage space */

typedef int KStatus;/* Status is the type of the function, and its value is the Status code of the function result, such as OK */
typedef int KElementType;/* KElementType The KElementType type depends on the actual situation; int */ is assumed here

// Define the node
typedef struct KNode{
    KElementType data;
    struct KNode *prior;
    struct KNode *next;
}KNode;

typedef struct KNode * LinkList; //5.1 Creating a bidirectional linkKStatus createLinkList(LinkList *L){
    
    //*L points to the header
    *L = (LinkList)malloc(sizeof(KNode));
    if (*L= =NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    
    // Add data
    LinkList p = *L;
    for(int i=0; i < 10; i++){Create a temporary node
        LinkList temp = (LinkList)malloc(sizeof(KNode));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        
        // create a bidirectional linked list for the new node
        //① Temp is the successor of p
        p->next = temp;
        // < p style = "max-width: 100%; clear: both
        temp->prior = p;
        // the last node of p should be recorded to facilitate the next insertion
        p = p->next;
        
    }
    
    return OK;
}

//5.2 Prints the elements of the circular list
void display(LinkList L) {LinkList temp = L->next;
    
    if(temp == NULL){
        printf("Printed bidirectional linked list is empty! \n");
        return;
    }
    
    while (temp) {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
    
}

//5.3 Insert elements into bidirectional lists
KStatus ListInsert(LinkList *L, int i, KElementType data){
    
    //1. Insert position is invalid 0 or negative
    if(i < 1) return ERROR;
    
    //2. Create a node
    LinkList temp = (LinkList)malloc(sizeof(KNode));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    
    //3. Point p to the header!
    LinkList p = *L;
    
    //4. Find the node directly inserted at position I
    for(int j = 1; j < i && p; j++) p = p->next;//5. If the insertion position exceeds the length of the list itself
    if(p == NULL) {return  ERROR;
    }
    
    //6. Check whether the insertion position is the end of the list;
    if (p->next == NULL) {
        
        p->next = temp;
        temp->prior = p;
    }else
    {
        //1️ PRIOR = temp on p->next
        p->next->prior = temp;
        //2️ retail temp->next points to original P ->next
        temp->next = p->next;
        //3️ retail -> Next update to newly created Temp
        p->next = temp;
        //4 newly created temp precursor = p ️
        temp->prior = p;
    }
    
    return  OK;
}

//5.4 Delete the node at the specified position in the bidirectional list
KStatus ListDelete(LinkList *L, int i, KElementType *e){
    
    int k = 1;
    LinkList p = (*L);
    
    //1. Check whether the bidirectional list is empty, if so, return ERROR;
    if (*L= =NULL) {
        return ERROR;
    }
    
  
    //2. Move the pointer p to the position before the deleted element
    while(k < i && p ! =NULL) {
        p = p->next;
        k++;
    }
    
    //3. Return ERROR if k> I or p == NULL
    if (k>i || p == NULL) {
        return  ERROR;
    }
    
    // create a temporary pointer delTemp to the node to be deleted, and assign the data of the node to *e
    LinkList delTemp = p->next;
    *e = delTemp->data;
    
    //5. P ->next equals the next node of the node to be deleted
    p->next = delTemp->next;
    
    //6. If the next node to be deleted is not null, then the precursor pointer to the next node to be deleted is assigned p;
    if(delTemp->next ! =NULL) {
        delTemp->next->prior = p;
    }
    
    // delete the delTemp node
    free(delTemp);
    
    return OK;
    
}

//5.5 Delete elements specified in the bidirectional list
KStatus LinkListDeletVAL(LinkList *L, int data){
    
    LinkList p = *L;
    
    //1. Loop through the bidirectional list
    while (p) {
       
        //2. Check whether the data field of the current node is equal to data. If so, delete the node
        if (p->data == data) {
            
            // Modify the successor pointer of the precursor node of the deleted node, refer to step 1️ on the figure
            p->prior->next = p->next;
            // Modify the precursor pointer of the successor node of the deleted node, refer to step 2️ on the figure
            if(p->next ! =NULL){
                p->next->prior = p->prior;
            }
            // Release node p
            free(p);
            // Exit the loop
            break;
        }
        
        // if this node is not found, continue to move pointer p
        p = p->next;
    }
    
    return OK;
    
}

//5.6.1 Finding elements in a bidirectional list
int selectElem(LinkList L.KElementType elem){
    
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == elem) {
            return i;
        }
        
        i++;
        p = p->next;
    }
    
    return  -1;
}

5.6.2 Update nodes in the bidirectional linked list
KStatus replaceLinkList(LinkList *L,int index,KElementType newElem){
    LinkList p = (*L)->next;
    
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    
    p->data = newElem;
    return OK;
}


void test () {
    KStatus iStatus = 0;
      LinkList L;
      int temp,item,e;
      
      iStatus =  createLinkList(&L);
      printf("iStatus = %d\n",iStatus);
      printf("List created successfully, print list :\n");
      display(L);
      
      printf("Please enter the insertion location \n");
      scanf("%d %d",&temp,&item);
      iStatus = ListInsert(&L, temp, item);
      printf("Insert data, print linked list :\n");
      display(L);
      
      printf("Please enter the insertion location \n");
      scanf("%d %d",&temp,&item);
      iStatus = ListInsert(&L, temp, item);
      printf("Insert data, print linked list :\n");
      display(L);
      
      printf("Please enter the insertion location \n");
      scanf("%d %d",&temp,&item);
      iStatus = ListInsert(&L, temp, item);
      printf("Insert data, print linked list :\n");
      display(L);
      
      printf("Please enter deleted location \n");
      scanf("%d",&temp);
      iStatus = ListDelete(&L, temp, &e);
      printf("Delete element: delete element at %d,data = %d\n",temp,e);
      printf("After delete operation, bidirectional linked list :\n");
      display(L);
      
      printf("Please enter what you want to delete \n");
      scanf("%d",&temp);
      iStatus = LinkListDeletVAL(&L, temp);
      printf("Delete node where data field = %d, bidirectional linked list :\n",temp);
      display(L);

      printf("Please enter what you are looking for \n");
       scanf("%d",&temp);
      KElementType index = selectElem(L, temp);
      printf(%d\n :%d\n :%d\n,temp,index);

      printf("Please enter the node you want to update and the content \n");
      scanf("%d %d",&temp,&item);
      iStatus = replaceLinkList(&L, temp, item);
      printf("Bidirectional linked list after updating node data :\n");
      display(L);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World! \n");
    test();

    return 0;
}


Copy the code

2. Bidirectional circular linked lists

2.1 Node Definition

The node definition of a bidirectional circular list is the same as that of a bidirectional list

// Define the node
typedef struct KNode{
    KElementType data;
    struct KNode *prior;
    struct KNode *next;
}KNode;
Copy the code

Table 2.2 built

Table building is actually the process of creating a non-empty linked list from an empty table based on the data we give it.

The following table defines an empty bidirectional linked list, where prior, next, and next point to itself:

Insert elements A and B from the end of the empty list. Insert elements B and A from the end of the empty list. Insert elements B and A from the end of the empty list.

The following code is a circular list creation process. In the code, we insert 0,1,2,3,4,5,6,7,8,9 elements by tail insertion.

//6.1 Bidirectional cyclic list initialization
KStatus creatLinkList(LinkList *L){
    
    *L = (LinkList)malloc(sizeof(KNode));
    if (*L= =NULL) {
        return ERROR;
    }
    
    (*L)->next = (*L);
    (*L)->prior = (*L);
    
    // Add data
    LinkList p = *L;
    for(int i=0; i < 10; i++){Create a temporary node
        LinkList temp = (LinkList)malloc(sizeof(KNode));
        temp->data = i;
        
        // create a bidirectional linked list for the new node
        //① Temp is the successor of p
        p->next = temp;
        // < p style = "max-width: 100%; clear: both
        temp->prior = p;
        //③ Temp is followed by *L
        temp->next = (*L);
        //④ p precedes the newly created temp
        p->prior = temp;
        //⑤ p should record the position of the last node to facilitate the next insertion
        p = p->next;
        
    }
    
    return OK;
   
}
Copy the code

2.3 Inserting nodes

The procedure for inserting a bidirectional circular list is as follows:

Find the precursor of the element to be inserted (as shown in the figure above, we find the precursor A of node B and point to A with p pointer).
Create a new node and assign it to CC and use temp to point to CC:temp->data = e;
The precursor node of temp is p:temp->prior = p;
Pointer to p->next:temp->next = p->next;
Let the successor of p point to the new node temp:p->next = temp;
Temp = temp; temp = temp; temp = temp;(*L)->prior = temp;; If not, the temp node is preceded by the temp node:temp->next->prior = temp;

The code for inserting nodes is as follows:

//6.2 Bidirectional circular linked list inserts elements
/* Insert into the end of the list when the insertion position exceeds the list length */
KStatus LinkListInsert(LinkList *L, int index, KElementType e){
   
    //1. Create pointer p to the bidirectional list header
    LinkList p = (*L);
    int i = 1;
    
    //2. If the bidirectional circular list is empty, error is returned
    if(*L= =NULL) return ERROR;
   
    //3. Find the node p inserted at the previous position
    while(i < index && p->next ! = *L) {
        p = p->next;
        i++;
    }
    
    //4. If I >index, error is returned
    if (i > index)  return ERROR;
    
    // create a new node temp
    LinkList temp = (LinkList)malloc(sizeof(KNode));
    
    //6. If temp is null, error is returned
    if (temp == NULL) return ERROR;
    
    //7. Assign e to temp data field.
    temp->data = e;
    
    // set temp to p;
    temp->prior = p;
    //9. Temp's successor points to p->next;
    temp->next = p->next;
    //10.p is a new node temp;
    p->next = temp;
    
    // If temp is not the last node
    if (*L! = temp->next) {//11. The next node of the temp node is preceded by the temp node
        temp->next->prior = temp;
    }else{(*L)->prior = temp;
        
    }
    
    return OK;
}
Copy the code

2.4 Deleting a Node

The process of deleting nodes in a circular double-linked list is as follows:

1. Find the node to delete (as shown above, temp pointer points to node B to delete)
2. Assign e to the data field of the node to be deleted:*e = temp->data;
3. Modify the successor pointer of the precursor node of the deleted node Figure 1️ discounttemp->prior->next = temp->next;(so the next of A, the precursor of B, points to C, the successor of B)
4. Modify the precursor pointer of the successor node of the deleted node Figure 2️ discounttemp->next->prior = temp->prior;(Let the precursor pointer of C, the successor of B, point to A, the precursor of B)
1. Alter table temp;free(temp);

The implementation code of circular double-linked list to delete nodes is as follows:

//6.4 Two-way circular linked list deletes nodes
KStatus LinkListDelete(LinkList *L,int index,KElementType *e){
    
    int i = 1;
    LinkList temp = (*L)->next;
    
    if (*L= =NULL) {
        return  ERROR;
    }
    
    // select *L from *L;
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    
    //1. Find the node to delete
    while (i < index) {
        temp = temp->next;
        i++;
    }

    //2. Assign e to the data field of the node to be deleted
    *e = temp->data;
    
    //3. Modify the successor pointer of the precursor node of the deleted node Figure 1️ retail
    temp->prior->next = temp->next;
    //4. Modify the precursor pointer of the successor node of the deleted node Figure 2️ one
    temp->next->prior = temp->prior;
    //5. Delete node temp
    free(temp);
    
    return OK;
    
}
Copy the code

2.5 traversal

//6.3 Iterate over the bidirectional circular linked list
KStatus Display(LinkList L) {if (L= =NULL) {
        printf("Printed bidirectional circular linked list is empty! \n\n");
        return ERROR;
    }
    printf("Contents of the bidirectional circular list:");
    
    LinkList p = L->next;
    while(p ! =L) {

        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n\n");
    return OK;
}
Copy the code

2.6 Unit Tests

void test() {
    LinkList L;
    KStatus iStatus;
    KElementType temp,item;
    
    iStatus = creatLinkList(&L);
    printf("Did the bidirectional circular list initialization succeed (1->YES)/ (0->NO): %d\n\n",iStatus);
    Display(L);
    
    printf("Input positions to be inserted and data separated by Spaces:");
    scanf("%d %d",&temp,&item);
    iStatus = LinkListInsert(&L,temp,item);
    Display(L);

    printf("Enter the location to delete:");
    scanf("%d",&temp);
    iStatus = LinkListDelete(&L, temp, &item);
    printf("Delete list location :%d, node data field :%d\n",temp,item);
    Display(L);
}
Copy the code