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

This article mainly introduces the use of single-linked list in c #, which has a certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading this article. Let's take a look at it.

No lead node linked list

One-way linked list is a kind of linked list. An one-way linked list consists of a series of nodes with discontiguous memory, each containing a field pointing to the value and a next pointer to the next node. The nextfield of the last node is null, which represents the end of the linked list.

The chain indicates the intention as follows:

First, the structure

1. Structure definition:

Struct LinkNode {void * x; struct LinkNode * next;}

2, structure size:

1) structure size method: sizeof (struct LinkNode); in 64-bit system, the structure size is taken out as: sizeof (struct LinkNode) = 16

2) Why it is 16 bytes: because this structure contains two pointer members x and next. The pointer stores the address, so under the same system platform, the sizeof size of the pointer variable is the same. That is, the size of the pointer variable does not depend on the pointer type, but on the system platform. 32 bits = 4 bytes, 64 bits = 8 bytes. Therefore, in a 64-bit system, sizeof (void *) = = sizeof (struct LinkNode *) = = 8. In a 32-bit system, sizeof (void *) = = sizeof (struct LinkNode *) = = 4.

3) if it is assumed that the node ABCD is continuous in memory and An is the starting point of memory, that is, the address of An is 0x00, then the address of BMagee C ~ D is 0x10 ~ ~ 0x20 ~ 0x30. And the next pointer of A points to node B (A-> next = & B), and so on until the next of node D stores null.

Second, creation of linked list

1, create a linked list (using first-level pointer)

Program description:

1) the program call method szyu_link_create1 ("AA", "BB", NULL), and NULL is used to terminate the for loop correctly.

2) create a new node node.

3) if the linked list is empty, first assign the new node (node) to head, and let last point to the latest head;. If the linked list is not empty, point the next of the tail node to the latest node, and re-assign the tail node.

Struct LinkNode*szyu_link_create1 (void * x,...) {struct LinkNode* head = NULL; struct LinkNode* last = head; va_list args; va_start (args, x); for (; x; x = va_arg (args, void *)) {struct LinkNode* node = NULL; node = (struct LinkNode*) malloc (sizeof (struct LinkNode)) If (node = = NULL) {return head;} node- > x; node- > next = NULL; if (head = = NULL) {head = node; last = head;} else {last- > next = node; last = node }} va_end (args); return head;}

2, linked list creation II (using secondary pointers)

Program description:

1) the secondary pointer node has the following equation: * node = = head,**node = * head

2) for has just started to create space for * node (* node = head), that is, a header node.

3) assign a value to the x of the (* node) node, and let the pointer node point to the next of the new node, that is, after the assignment, * node is the next domain value of the previous node.

4) starting from the second for, the assignment to * node is to (* node)-> next.

5) repeat step 3 and 4 until NULL is introduced.

6) after the last node points node to next, it does not assign NULL value to it. Therefore, NULL is assigned to * node at the end of the for loop. Represents the end of the linked list.

Struct LinkNode*szyu_link_create2 (void * x,...) {struct LinkNode* head = NULL; struct LinkNode* * node = & head; va_list args; va_start (args, x); for (; x; x = va_arg (args, void *)) {(* node) = (struct LinkNode*) malloc (sizeof (struct LinkNode)) If ((* node) = = NULL) {return head;} (* node)-> x = x; node = & (* node)-> next;} * node = NULL; va_end (args); return head;}

3, comparison between first-level pointer and second-level pointer

First-order pointer

1) advantages: the program is easy to understand.

2) disadvantages: the way to insert the header node is different from that of other locations, and the code style is not uniform.

Secondary pointer

1) advantage: no matter where it is inserted, the code style is highly uniform. The code is simplified.

2) disadvantage: high skill.

4. Design ideas.

The use scenario of the second-level pointer is to "indirectly change the memory address pointed to by the first-level pointer". The changed first-level pointer points to the next pointer. The new addresses of all nodes except the header node are stored in the next of the previous node. The inherent design node points to next, and next is assigned when * node is assigned.

Third, linked list insertion

1, insert one into the linked list (using first-level pointer)

Program description:

1) the judgment of key ensures that the input position can not be less than 1, and a new node can be inserted at the end of the linked list.

2) initialize the new node.

3) int cnt = 2; when key = 1, the first node is reinserted; the previous node inserted when key = 2 is the first node. So in key len) {return head;} struct LinkNode * node = NULL; node = (struct LinkNode *) malloc (sizeof (struct LinkNode)); if (node = = NULL) {return head;} node- > x = x; node- > next = NULL; struct LinkNode * list = head; int cnt = 2; for (; cnt

Next;} if (key = = 1) {node- > next = head; head = node;} else {node- > next = list- > next; list- > next = node;} return head;}

2, insert two into the linked list (using secondary pointer)

Program description:

1) key-1 ensures that the node is inserted properly after the linked list.

2) due to the use of secondary pointers, the cnt can be initialized to 1, and there is no need to consider inserting the header node separately.

Struct LinkNode * szyu_link_insert2 (struct LinkNode * head, void * x, int key) {if (head = = NULL) {return head;} int len = szyu_link_length2 (head); if (key)

Len) {return head;} struct LinkNode * * list = & head; int cnt = 1; while (cnt

Next; cnt + = 1;} struct LinkNode * remain = * list; * list = (struct LinkNode *) malloc (sizeof (struct LinkNode)); if ((* list) = = NULL) {return head;} (* list)-> x; (* list)-> next = remain; return head;}

3. Use the advantages and disadvantages of first-level pointer and second-level pointer to create the same linked list.

4, the design idea of using two-level pointer

1) first make the second-level pointer list point to the first-level pointer head.

2) Recycling the linked list stays on the previous node of the insertion position. In this case, if it is not the position of the header node, list points to the next of the node before the insertion position. When inserting, you only need to assign a new node address to * list. If it is a header node, * list points to the header node.

3) whether it is a header node or not, assign the rest of the linked list to remain (if inserted as a header node, remain retains the entire linked list; if inserted at the end, remain is NULL).

4) assign a new node address to * list. And append the remain to the * list node.

Fourth, delete the linked list node

1, delete the linked list node (first-level pointer)

Program description:

1) if the header node is to delete the node, just point the head to head- > next.

2) since delete stays in front of the node to be deleted, you only need to assign delete- > next to remain, and you can do so in free.

Struct LinkNode*szyu_link_delete1 (struct LinkNode* head, void * x) {if (head = = NULL) {return NULL;} struct LinkNode* delete = head; struct LinkNode* remain = NULL; if (strcmp ((char *) delete- > x, (char *) x) = = 0) {remain = delete; head = delete- > next } else {while (delete- > next! = NULL & & strcmp ((char *) delete- > next- > x, (char *) x)! = 0) {delete = delete- > next;} remain = delete- > next; delete- > next = delete- > next- > next;} free (remain) Return head;}

2, linked list node deletion (secondary pointer)

Program description

1) if it is a header node, * list = head,head = head- > next, which means * list = (* list)-> next.

2) if it is not a header node, list is the pointer to next, and * list is the next node. To delete the next node, re-assign the value to * list to change the direction of the next node.

Struct LinkNode*szyu_link_delete2 (struct LinkNode* head, void * x) {if (head = = NULL) {return head;} struct LinkNode* * list = & head; while ((* list)! = NULL & & strcmp ((char *) (* list)-> x, (char *) x)! = 0) {list = & (* list)-> next;} struct LinkNode* remain = * list (* list) = (* list)-> next; free (remain); return head;}

Fifth, linked list release

Program description:

1) the * head after using the secondary pointer is to delete the node.

Voidszyu_link_free2 (struct LinkNode * * head) {if (* head = = NULL | | head = = NULL) {return;} struct LinkNode * next = NULL; for (; * head; * head = next) {next = (* head)-> next; free (* head);}}

Sixth, obtain the length of the linked list.

Program description:

1) because the linked list does not take the lead node, it directly assigns the head linked list.

Intszyu_link_length2 (struct LinkNode * head) {if (head = = NULL) {return 0;} struct LinkNode * pLen = head; int len = 0; for (; pLen! = NULL; pLen = pLen- > next) {len + = 1;} return len;}

Seventh, linked list printing

Voidszyu_link_print1 (struct LinkNode * head) {if (head = = NULL) {return;} struct LinkNode * print = head; for (; print! = NULL; print = print- > next) {printf ("% s", (char *) print- > x);} printf ("\ n") } Thank you for reading this article carefully. I hope the article "what is the use of a single linked list in c #" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.