Single linked list structure

#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;        // Single-linked lists store the data types of elements

// Define a single list structure
typedef struct Node(a){
    ElemType data;            // Single linked list node data field
    struct Node *next;        // single list node address field (pointing to the next node)
}*LinkList, Node;
Copy the code


Head plug method to construct a single – linked list

Code implementation

/* * header method to create a single list (head node) * datas receive array, used to assign list node data * len datas array length, easy traversal */
LinkList CreateHeadListH(ElemType *datas, int len){
    // Create a header
    LinkList head, new_node;
    head = (LinkList)malloc(sizeof(Node));
    // head -> data = len; // The list length can be stored in the header data field
    head -> next = NULL;

    // Assign new nodes and use header linking
    for(int i=0; i<len; i++){ new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = head -> next;
        head -> next = new_node;
    }
    return head;
}
Copy the code


Head insertion process

Insert into the head of a single list, assuming

datas[] = {2.4.6};
Copy the code

First, create the header

When the first new node is allocated

Head -> next = NULL; head -> next = NULL;

new_code -> data = datas[0];         -->        new_code -> data = 2;
new_code -> next = head -> next;    -->        new_code -> next = NULL;
Copy the code

And then let theheadThe address field of the node points to the new node (in this case, the first node).

head -> next = new_code1;
Copy the code

Eventually form

When you assign the second new node

Head -> next = new_node1; head -> next = NULL;

new_code -> data = datas[1];        -->        new_code -> data = 4;
Copy the code

Set the address field of the second node to the first node (the first node has the address field of the head node).

new_code -> next = head -> next;    -->        new_code -> next = new_code1;
Copy the code

Then make the address field of the head node point to the location of the second node

head -> next = new_code2;
Copy the code

Eventually form

After assigning the third new node

The key code

Every time you insert a new node, you insert into the head node.

new_node -> next = head -> next;    // set the address field of the new node to the address field of the header node
head -> next = new_node;            // Then make the address field of the header point to the new node location
Copy the code

This cycle forms a single – linked list using the head – plug method.


Tail insertion method to construct a single – linked list

Code implementation

/* * The end method creates a single list (head node) * datas receive array, used to assign the list node data * len datas array length, easy traversal */
LinkList CreateHeadListT(ElemType *datas, int len){
    // Create a header
    LinkList head, p, new_node;
    head = (LinkList)malloc(sizeof(Node));
    head -> next = NULL;
    p = head;

    // Assign new nodes and connect them with a tail method
    for(int i=0; i<len; i++){ new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = NULL;
        p -> next = new_node;
        p = new_node;
    }
    return head;
}
Copy the code


Tail insertion process

The tail insertion method inserts the end of the single linked list, again assuming that the node data of the single linked list are respectively.

datas[] = {2.4.6};
Copy the code

Creating a header is the same thing as doing a header insertion and I’m not going to repeat it.

When I assign the first new node

Head -> next = NULL; head -> next = NULL; The variable p is equal to the head p = head; .

Let’s get the new node assigned

new_code -> data = datas[0];        -->        new_code -> data = 2;
new_code -> next = NULL;            -->     new_code -> next = NULL
Copy the code

Let the list be linked

p -> next = new_code;
p = new_code;
Copy the code

At first p = head, so make the address field of the head point to the new node, and then make p equal to the new node (where the new node represents the first node).


When you assign the second new node

Head -> next = new_node1; head -> next = NULL;

Now the variable p is equal to the first node, not the head node.

We continue to have new nodes linked to a singly linked list

p -> next = new_code;
p = new_code;    
Copy the code

Let the address field of the first node point to the new node (where the new node represents the second node) and let p be equal to the second node.


After assigning the third new node

The key code

p -> next = new_code;    // make p's address field point to the new node
p = new_code;            // Then set p equal to the new node (always equal to the last node)
Copy the code

Every time you insert a new node, you insert it toward the end node.

This cycle forms a single – linked list constructed by tail insertion.


Single chain list head and tail insertion method comparison

Datas [] = {2, 4, 6, 8}; But the effect of linking is inconsistent and the idea is different.

Head insertion: head –> 8 –> 6 –> 4 –> 2

Nodes are inserted all the way to the head of a single linked list, and the data node entered first is linked at the end (just in reverse order), a bit like a stack.

Tail insertion: head –> 2 –> 4 –> 6 –> 8

Nodes are inserted all the way to the end of the list, and the data node entered first is still in front.


The source code

The source code has been uploaded to GitHub data-structure-of-C, welcome to visit.

✍ code word is not easy, the long journey always feeling, praise again go line, also hope you heroes support ❤️