Linear one-way linked table

preface

In the last two weeks, I began to learn Pointers and structures, and took some time to sort out the linked list. Linear list Linked storage structure includes single linked list, double linked list, circular linked list and ordered list this kind of linear list, single linked list of the basic operation of the implementation and there are many kinds, in code implementation we have different statements and logic. Here we only discuss the linear one-way linked list of common knowledge points and operations to achieve the method (refer to the C language programming foundation –> data structure tutorial) in writing linked list of procedures, we usually write a function, and then call the function.

An overview of linked lists

The chain storage structure of a linear list is called a linked list. Each storage node contains a data domain and a pointer domain. When using chain storage, only one pointer domain is set in each node to point to the subsequent nodes in addition to the data domain. Head pointer: Each linked list has a head node, which is uniquely identified with the pointer of the Palace Museum’s head node, and is called the head pointer. Beginning pointer: A pointer to the beginning or beginning node is called a beginning pointer. Tail pointer: Pointers to tail nodes are called tail Pointers.

Storage density = the amount of data elements in a node the amount of data elements in a node <1. The storage capacity of data elements in a node is less than 1.

Two, the basic use of single linked list

(1) declare node type

Node types are declared in a structure that stores data and Pointers to the next node.

struct node
{
    int value;// Store the data of the node
    struct node *next;// Pointer to the next node
 };
Copy the code

The way structures are declared, we also use a different way of declaring nodes

typedef struct LNode/ / usetypedefDo not omit nodes when declaring themLNode, there is noLNodeThe tag cannot be declarednextType {
    ElemType value;
    struct LNode *next;
}Linknode;
Copy the code

In the first case, after declaring the node type, we get something like this

Analogous to a linear bidirectional list, there are two Pointers inside a structure, one pointing and one pointing

struct node
{
   int value;
   struct node *last;
   struct node *next;
};
Copy the code

So what we get is a structure that looks like this

We need a pointer to the beginning of the list, the variable that always points to the first node

struct node *first = NULL;
Copy the code

(2) Create nodes

Allocate memory space for the node; store data in the node; insert the node into the linked list. At this point we need a transient variable to point to the node until the node is inserted into the linked list

struct node *new_node;// Create a new pointer to the insert node
new_node = malloc(sizeof(struct node));// Allocate memory space dynamically for new nodes, and sizeof () is the type to be allocated
Copy the code

The new_node pointer now points to such a block of memory as the next node structure

Then we store the data in the new node in two ways

(*new_node).value = 10;// This is the usual way to access a member name in a structure
new_node->value = 10;// This is the combination of the * and. Operators to achieve the same purpose (more convenient method)
Copy the code

(3) Insert nodes at the beginning of the linked list

The process of inserting a new node consists of two statements

new_node->next = first// The next pointer points to the first existing node
first = new_node;// Make first point to the new node, so that the new node is inserted to the left
Copy the code

The illustration is as follows:

I’m going to insert 10 and 20 nodes in order to understand the process of inserting new nodes, and I’m going to go straight to the example, and it’s going to be very clear when I understand the diagram. Let’s assume that the linked list is empty when the node is inserted.

Each time a new node is inserted, the pointer new_node, which is used to temporarily point to the new node, does its job and needs to be reallocated before the next node is inserted. Repeat the above procedure to insert the node from the start of the list.

(4) write a function to insert nodes

struct node *add_to_list(struct node *list,int n)//list is a pointer to the first node of the old list, where n is the inserted data
{
   struct node *new_node;
   new_node = malloc(sizeof(struct node));
   if(new_node == NULL)// Check whether the dynamically allocated new_node pointer is null
   {
      printf("Error.");
      exit(EXIT_FAILURE);
   }
   new_node->value = n;// assign n to value in new_node
   new_node->next = list;// The next pointer to the new node points to the original list
   return new_node;
   List =new_node =new_node =new_node =new_node =new_node
   // But at the end there is a return new_node statement that returns new_node to the list, thereby updating the list
Copy the code

Schematic diagram is as follows:

: actually, I think this way of inserting new node looks like tRNA mode of transport, in order to join and then continue to transport, carry on tRNA three amino acid is one of the three members of the node, and tRNA connection way to transport amino acids on the mRNA is short link to the long chain of peptide chain, the chain table when node in the left side of the new from the old chain (reverse)

Insert data and call the function directly

add_to_list(first,10);// The actual argument first is the list above, and the inserted data is 10
add_to_list(first,20);/ / same as above
Copy the code

PS. We need to note that the nodes inserted in this way are in reverse order, and the last node inserted is at the far left

(five) write a user input number function

Using the existing function above to insert the new node, we can let the user do the input operation

struct node *read_numbers(void)
{
   struct node *first = NULL;
   int n;
   printf("Enter a series of numbers:");
   for(;;)
   {
      scanf("%d",&n);
      if(n == 0)// The defined input n==0 ends the loop and returns directly
      {
         return first;// The end command returns to the list to end the loop
      }
      first = add_to_list(first,n);// The linked list is updated with each loop
}
Copy the code

(6) Search linked list

The flexibility of the for loop makes it our preferred for loop to iterate over the elements of the list and use a pointer P to track the current node position

struct node *search_list(struct node *list,int n)
{
   struct node *p;// use pointer p to track nodes
   for(p = list; p ! =NULL; p = p->next) {if(p->value == n)
      {
         returnp; }}return NULL;// If n is not found, a null pointer is returned
}
Copy the code

Delete nodes from the linked list

Three steps: 1, locate the node to be deleted 2, change the previous node, let it bypass the node to be deleted and point to the next node 3, call the free function to recover the memory space occupied by the deleted node the most direct idea of course is to search the linked list method to locate the node to be deleted data, but! When the add_to_list function reaches n, the search stops and return, and the subsequent operation bypassing the delete point cannot be performed. You just add a trace pointer, so one of the trace Pointers points to the current node, and the other pointer points to the one in front of that node, which is the precursor of the pointer

sturct node *delecte_from_list(struct node *list,int n)
{
   struct node *cur, *prev;
   for(cur = list,prev = NULL; cur ! =NULL&& cur->value ! = n; prev = cur,cur = cur->next);// Start with cur pointing to the list, prev empty, and run when cur has not moved to the end of the list or n
   // Notice the for loop here! Is a separate for (); Judge after the search is over
   // At the end of each loop cur is assigned to prev, and cur moves back one node, so cur is still the successor of Prev
   if(cur == NULL)// If cur is not found at the end of the list, it is not found at the end
   {
      return list;
   }
   if(prev == NULL)// If prev is empty, prev has not joined the battle yet. List points to the next node
   {
      list = list->next;
   }else{
      prev->next = cur->next;
      // The node before the delete point points to the next node in cur
   }
   free(cur);// Call free to reclaim the memory it occupies
   return list;
}
Copy the code

There is another way to bypass the deletion node and use the pointer P to track the location of the node. The following process is performed at a, the precursor node of the deletion node B

The bypass process is shown as follows:

There is another code that can be used to delete nodes

p->next = p->next->next;// use a pointer p to locate the deleted nodes and bypass the nodes to join the new list
free(p->next);// delete the node where b is located
Copy the code

The schematic diagram is as follows:

After deleting nodes from the linked list:

PS. To delete a node in a single linked list, you need to find its precursor!

Establishment of single linked list: Head plug method tail plug method (with data structure briefly)

The above method requires the master of the first semester of the freshman, the following content is followed by the following part of the data structure foundation

Realization of common operations in single linked list (data structure)

We declare a structure as follows

typedef struct LNode// To declare Pointers in the structurenext
{
   ElemType data;
   struct LNode *next;
}LinkNode;
Copy the code

(1) Initialize the linear table

// Create an empty link table time complexity O(1)
void InitList(LinkNode *&L)
{
   L=(LinkNode *)malloc(sizeof(LinkNode));
   L->next = NULL;// create a header. Next is NULL
}
Copy the code

(2) Destroy the linear list

Free the memory space occupied by the entire single linked list L, free the space of all nodes one by one. Using two adjacent Pointers (cur and prev), prev points to the precursor of cur (prev points to the head, cur to the head), is similar to using two Pointers to locate and delete the node and bypass the process. When cur is not null, the loop is performed to release prev. Then prev and cur move one node backwards at the same time. At the end of the loop, the prev points to the tail node, and then the preV is released.

// Time complexity O(n), where n is the number of nodes in the linked list
void DestroyList(LinkNode *&L)
{
   LinkNode *prev = L,*cur = L->next;
   while(cur! =NULL)// Scan the linked list
   {
      free(prev);
      prev = cur;
      cur = prev->next;// These two statements can move both cur and prev back a node at the same time
   }
   free(prev);// Cur is NULL and prev points to the end of the loop
}
Copy the code

The illustration is similar to deleting nodes in a linked list with two Pointers

(3) find the length of the linear table

// Time complexity O(n)
int ListLength(LinkNode *L)
{
   int n=0;
   LinkNode *p = L;//p points to the header
   while(p->next ! =NULL)
   {
       n++;// Count in sequence
       p = p->next;
   }
   return n;
}
Copy the code

(4) Output linear table

// Time complexity O(n)
void DispList(LinkNode *L)
{
   LinkNode *p = L->next;// Start with a header pointer instead of a header pointer
   while(p ! =NULL)
   {
      printf("%d",p->data);// Print the data stored in the node pointed to by p
}
Copy the code

The following linked list operation methods are briefly summarized: (5) judge whether the linear list is empty (6) find the value of a certain data element in the linear list (7) search by the value of the element (8) Insert data element (9) delete data element