In # 01– Basic knowledge of data structures and algorithms has been introduced about the basic knowledge of data structures and algorithms, need to understand the friends please move.

First, the design of one-way linked list

Features of chain storage:

  • There are onlyThe first oneElements andThe last oneElements;
  • All elements except the first and last have oneprecursorAnd asubsequent;
  • The first element has no precursor, only follow-up, and the last element has precursor, no follow-up.

The memory address of each node in the linked list is discontinuous, so we can find the next node through the current node. Combining the characteristics of linear structure and chain storage, we design a one-way linked list.

2, preparation,

Design some state values and data types as state callbacks to function calls

#define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 */ typedef int Status; / / typedef int ElemType; / / typedef int ElemType; /* ElemType specifies the value of the value. The value is assumed to be int */Copy the code

3. Design of nodes

Features of unidirectional linked lists:

  • There areThe onlytheThe firstA node and theThe lastA node, let’s call itThe first element nodeandEnd node;
  • Except for the leading and trailing nodesOther nodesThere is aprecursorAnd asubsequent;
  • The first element nodeOnly the followingThere is no precursor;
  • End nodeOnly the precursorThere is no follow-up.

The nodes of a one-way list contain a data field, which records the data that the node needs to record, and a pointer field, which points to the next node:

According to the characteristics of unidirectional linked lists, we design the following data structures as nodes of unidirectional linked lists:

typedef struct Node{ ElemType data; Struct Node *next; // Pointer field}Node; typedef struct Node * LinkList; // Rename the node typeCopy the code

When designing a one-way linked list, there are two design scenarios: the leading node and the unled node. The so-called head node is to place a node that does not record any data at the front of the linked list, and facilitate the insertion and deletion of the first node through the head node.

1. Do not have the lead node

2. Primary node

Note: The following code logic is based on a one-way linked list of leading nodes.

Four, create,

*L = (LinkList)malloc(sizeof(Node)); *L = (LinkList)malloc(sizeof(Node)); If (*L == NULL) return ERROR; (*L)->next = NULL; return OK; }Copy the code

When creating a unidirectional linked list, create a node through malloc, point *L to this node, and point next to NULL. At this time, the unidirectional linked list has only one node, which is both the first and last node.

When creating a linked list, multiple data may be inserted, and data is generally inserted at the head of the list and at the tail of the list in two ways, we call the head interpolation method and the back interpolation method

1. Forward interpolation

As shown in the figure above, interpolation means that the newly inserted element is inserted into the first position, the position of the head node, making it the new head node.

Code implementation:

void CreateListHead(LinkList *L, int n){ LinkList p; *L = (LinkList)malloc(sizeof(Node)); *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; For (int I = 0; i < n; P = (LinkList)malloc(sizeof(Node)); P ->data = I; P ->next = L->next = (*L)->next; // Next points to the new node, making the new node the first node (*L)->next = p; }}Copy the code

The data inserted by the forward interpolation method will be inserted at the position of the first node, so the resulting one-way list is a reverse list.

2, after insertion method

As shown in the figure above, post-insertion means that the newly inserted data is inserted to the tail of the linked list. To facilitate insertion, the tail node needs to be recorded after each insertion, so that the next point of the original tail node can be directly pointed to the new node when data is inserted next time, making the new node become the new tail node.

Code implementation:

void CreateListTail(LinkList *L, int n){ LinkList p,r; *L = (LinkList)malloc(sizeof(Node)); //r = *L; for (int i=0; i<n; P = (Node *)malloc(sizeof(Node)); p->data = i; R ->next = p; R = p; } next = NULL r->next = NULL; }Copy the code

The data inserted by the back interpolation method is inserted at the position of the tail node, so the resulting one-way list is a sequential list.

Five, insert the specified position

If you want to insert a node Cooci where Hank is located, you need to find the CC node first. Create a new node, Cooci, where next points to Hank and next points to Cooci.

Code implementation

Status ListInsert(LinkList *L,int i,ElemType e){ int j; LinkList p,s; p = *L; j = 1; While (p &&j < I) {p = p->next; ++j; } // There is no node in the position to insert, insert invalid if(! p || j>i) return ERROR; // Create a new Node s s = (LinkList)malloc(sizeof(Node)); s->data = e; S ->next = p->next; P ->next = s; return OK; }Copy the code

The importance of the head node comes into play when inserting data into a one-way list. The key to insert data is to find the precursor of the target location. In the case of a head node, all nodes including the first element node have a precursor, so for any location of the insert, the code implementation logic can be written uniformly.

Six, delete,

To delete the Hank node, you need to find the Hank node and its precursor CC node, point next of the CC node to the next Cooci node of the Hank node, and then release the Hank node.

Status ListDelete(LinkList *L,**int** i,ElemType *e){ int j; LinkList p,q; p = (*L)->next; j = 1; While (p->next &&j <(i-1)) {p = p->next; ++j; } // if (I >n or I <1) (p->next) || (j>i-1)) return ERROR; //q = p->next; P ->next = q->next; E *e = q->data; // Let the system reclaim this node, free memory; free(q); return OK; }Copy the code

When deleting a node, the most critical thing is to find the precursor of the target node, which also reflects the importance of designing the head node.

Seven, query

Status GetElem(LinkList L,int I,ElemType *e){//j: count. // declare node p; LinkList p; // point node P to the first element of list L; p = L->next; / / j calculation = 1; j = 1; While (p && j< I) {//p points to the next node p = p->next; ++j; } // If p is empty or j> I, error if(! p || j > i) return ERROR; // data *e = p->data; return OK; }Copy the code

Query the most critical judgment finally found the corresponding node.

Eight, traverse

Status ListTraverse(LinkList L)

{
    LinkList p=L->next;

    while(p)
    {
        printf("%d\n",p->data);
        p=p->next;

    }
    printf("\n");

    return OK;
}
Copy the code

Traversal finds the next node through next of the current node. When next points to NULL, the traversal is complete.

Nine, empty

Status ClearList(LinkList *L)
{

    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */

    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }

    (*L)->next=NULL;        /* 头结点指针域为空 */

    return OK;
}
Copy the code

To clear the linked list, start from the first node, first find the follow-up of the current node, and then release the current node; Loop until the current node is NULL. Finally, you need to point next of the head node to NULL.

Ten, the general section

Designing a head node when designing unidirectional linked lists can help us design more efficient deletion and insertion algorithms. Forward and back interpolation are also the focus of unidirectional lists.