Shulou(Shulou.com)06/01 Report--

This article mainly introduces "what is the linear linked list of C language linear list". In the daily operation, I believe that many people have doubts about what the linear linked list of C language linear list is. The editor consulted all kinds of data and sorted out the simple and easy-to-use operation method. I hope it will be helpful to answer the doubt of "what is the linear linked list of C language linear list?" Next, please follow the editor to study!

Define

The linked list stores the data elements in the linear table through a set of arbitrary storage units, each node contains two fields: the domain in which the information of the data elements is stored is called the data field, and the domain in which the addresses of its subsequent elements are stored is called the pointer domain. Therefore, the linear list of n elements is connected into a "chain" by the pointer field of each node, which is called the linked list. If each node of the linked list contains only one pointer domain, it is called a linear linked list or a single linked list.

The linked storage structure of a linear table does not need to be implemented by address contiguous storage units, because it does not require that two logically adjacent data elements are physically adjacent. It establishes the logical relationship between data elements through pointers.

The linked list is made up of nodes, which are defined as follows:

Typedef struct node {DataType data; struct node * next;} Linklist

Access to a linear linked list must start with the header pointer, which indicates the storage unit of the first node in the linear linked list. Because the last data element of the linear table does not have a direct successor, the pointer field of the last node in the linear linked list is NULL.

For convenience, a node (called header node) can be added in front of the first element, the data field of this node is empty, and the storage address of the node (header node) where the first element of the linear list is stored in the pointer domain. If the table is empty, the pointer field is empty.

Therefore, empty linked lists are also divided into empty linked lists with header nodes and empty linked lists without leading nodes. If there is a header node, the data field of the header node is empty and the pointer field is empty, the linked list is an empty linked list; if there is no header node and the header pointer is a null pointer, the linked list is an empty linked list.

1. insert

Suppose the two data elements an and b of the online table are inserted with a pointer to node a. In order to insert the data element x, we first need to generate a new node with the data field x, s is the pointer to the new node, and then the pointer field of the new node points to b (p-> next), and the pointer field of node a points to the new node (s).

Int InsertLinkList (LinkList * H, int I, DataType x) / * insert the element x\ x / {LinkList * p; LinkList * s; int j = 0; p = H; while (p & & jnext; jacks;} / * loop until p points to the I-1st element * / if (! P) return-1) in the linear linked list H with a head node. / * I is greater than the table length plus 1 seconds / s = (LinkList *) malloc (sizeof (LinkList)); s-> data = x; s-> next = p-> next;/* inserts data elements xlength / p-> next = s; return 1;} 2. Establish linear linked table 1) head insertion method

The establishment of a linear linked list should start with an empty list, apply for a node for each data element read, and then insert it between the head node of the linked list and the first node. The header node is H and the application node is s. According to the above insertion algorithm, the operation steps are as follows:

S-> next = H-> next; H-> next = s

Coupled with the steps of creating a new header node, reading data elements, and applying for a node, the programmability is as follows:

LinkList * CreateLinkList_front () {LinkList * Hash raceme H denotes the header node * / LinkList * s; char xbank * sets the data element type as char*/ H = (LinkList *) malloc (sizeof (LinkList)); / * applies for memory space for the header node * / H-> next = NULL; scanf ("% c", & x) While / * flag is the flag to end the creation process, such as'# 'and other * / {s = (LinkList *) malloc (sizeof (LinkList)); s-> data = x; s-> next = H-> next; H-> next = s; scanf ("% c", & x);} return H;}

Because it is inserted at the head of the linked list, the order in which the data is read is the opposite of the logical order in the linear table.

2) tail insertion method

The method of establishing a linear linked list by inserting in the header is simple, but the order of reading the data elements is opposite to that of the elements in the generated linked list. If you want the order to be the same, use the tail interpolation method. Because each time you insert a new node at the end of the linked list, you need to add a pointer to always point to the tail node in the linked list so that the new node can be inserted at the end of the linked list.

Earlier, we introduced the insertion algorithm, where you can call the insertion algorithm by defining a variable int I = 1 position, calling the previous function InsertLinkList (H, I, x); every time you insert a data element, you make the insertion cross cross, so that you can always insert at the end of the linked list.

LinkList * CreateLinkList_rear () {LinkList * H; DataType x role * Let DataType be the type of data element * / int I = 1; H = (LinkList *) malloc (sizeof (LinkList)); H-> next = NULL; scanf (& x); / * value of read-in data element * / while (xcoded flag) {InsertLinkList (H, I, x); / * call insertion algorithm * / iBeck + Scanf (& x);} return H;}

But this makes the time complexity of the algorithm an order of magnitude higher than that of plug-in, because every time a data element is inserted at the tail, the InsertLinkList () function is called again to make the pointer point to the tail node again from the header pointer.

So we can keep the pointer (marked p) pointing to the tail node in the linked list, and then have the new node (marked s) insert the tail of the linked list according to the insertion algorithm. You can simply modify the while loop of the above code:

LinkList * CreateLinkList_rear () {LinkList * H, * p, * s; DataType xbank * Let DataType be the type of data element * / H = (LinkList *) malloc (sizeof (LinkList)); H-> next = NULL; scanf (& x); / * value read into the data element * / p = H; while (xcoded flag) {s = (LinkList *) malloc (sizeof (LinkList)); s-> data = x S-> next = NULL; p-> next = s; p = p-> next; scanf (& x);} return H;} 3. Delete

Suppose there are three data elements a, b, c in the linked list. To delete the data element b between the data element an and the data element c, you only need to modify the pointer field of the node where the data element an is located. Suppose the pointer p points to the data element a, and the phrase means:

P-> next = p-> next- > next

Add a pointer variable Q to point to the data element B. when you change the pointer field of the node where the data element an is located, the memory of Q can be freed, that is, the memory occupied by the data element b can be freed. Furthermore, the flag variable I is passed in when the function is called, which can delete the I data element.

Int DeleteLinkList (LinkList * H, int I) / * deletes the I element * / {LinkList * p; LinkList * q; int j = 0; p = H; while (p-> next & & jnext; jacks;} / * loop until p points to the I-1st element * / if (! (p-> next)) return-1 / * invalid delete node * / Q = p-> next; p-> next = Q-> next;/* delete I data element * / free (Q); / * release the memory occupied by the I data element * / return 1;}

Comparing the insertion algorithm with the deletion algorithm, the function of the while loop is also to make p point to the I-1 element. Why is the loop condition of the insertion algorithm p & & jnext & & jnext; return p;}?

To return the order of a node with a value of x in the linked list, you can use a marker variable I to record the order of the node; if not, return-1. The modification procedure is as follows:

Int SearchLinkList (LinkList * H, DataType x) / * looks for the node with the value x in the linear linked list H, and returns its order in the linked list after finding it. Otherwise, it returns-1 values / {LinkList * p = H-> next;/*p points to the first data element of the linear linked list * / int I = 1; while (paired null & p-> dataroomx) {p = p-> next; ielements + } if (p! = NULL) return i; else return-1;} 5. Find the table length of a linear linked list

Let H be a linear linked list of leading nodes (the length of the linear list does not include the head node). The operation of finding the table length of the linear linked list is similar to the order of finding a node in the linked list.

Int LinkListLength (LinkList * H) {LinkList * p = HX * p = HX * * p points to the node * / int n = 0; while (p-> next) {p = p-> next; n;} / * p refers to the nth node * / return n; at this point, the study of "what is the linear linked list of C language linear list" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.