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

This article mainly introduces "how to realize the C++ lead two-way circular linked list". In the daily operation, I believe many people have doubts about how to realize the two-way circular linked list led by C++. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about how to realize the two-way circular linked list led by C++. Next, please follow the editor to study!

The difference between single linked list and single linked list

Unidirectional / bidirectional

One-way: there is only one next pointer to the next element

Bi-directional: there are two pointers pointing to the previous and next elements, so it is convenient to find the previous node and the latter node

Take the lead / not take the lead

Lead: there is a Sentinel node as the header node before the original header node. Its address range pointer points to the header node, and the value range is not used.

Do not take the lead: there is no Sentinel head node, in the tail deletion, tail insertion and other issues to consider the situation of the head node (limitation)

Cyclic / acyclic

Loop: the head node is connected to the tail node

Acyclic: the head node is not connected to the tail node

Code implementation interface / / create linked list (list initialization) ListNode* ListCreate (); / create node ListNode* BuyListNode (ListNode* pHead); / / Bidirectional linked list destroy void ListDestory (ListNode* pHead); / / Bidirectional linked list print void ListPrint (ListNode* pHead); / / Bidirectional linked list tail insert void ListPushBack (ListNode* pHead, LTDataType x); / / Bidirectional linked list tail deletion void ListPopBack (ListNode* pHead) / two-way linked list inserts void ListPushFront (ListNode* pHead, LTDataType x); / / two-way linked list header deletes void ListPopFront (ListNode* pHead); / / two-way linked list lookup ListNode* ListFind (ListNode* pHead, LTDataType x); / / two-way linked list inserts void ListInsert (ListNode* pos, LTDataType x) in front of pos; / / two-way linked list deletes node void ListErase (ListNode* pos) at pos location; node construction typedef int LTDataType;typedef struct ListNode {LTDataType data Struct ListNode* next; struct ListNode* prev;} ListNode; initialize linked list / / create linked list (initialize) ListNode* ListCreate () {/ / Open Sentinel head node ListNode* plist = (ListNode*) malloc (sizeof (ListNode)); if (plist = = NULL) / / failed to print error message and end process {perror ("ListCreat fail:") Exit (- 1);} plist- > next = plist; plist- > prev = plist; return plist;} Open Node / / create Node ListNode* BuyListNode (LTDataType x) {/ / create Node ListNode* newnode = (ListNode*) malloc (sizeof (ListNode)) If (newnode = = NULL) / / failed to print error message and end process {perror ("creatnode fail:"); exit (- 1);} newnode- > data = x; / / initialize node newnode- > next = NULL; newnode- > prev = NULL; return newnode;} destroy linked list

Note: dynamically opened linked list spaces need to be released after they are not in use to avoid memory leaks.

/ / destroy void ListDestory (ListNode* pHead) {/ / assert that the incoming pointer is not NULL assert (pHead); ListNode* cur = pHead; pHead- > prev- > next = NULL; while (curving null) {ListNode* next = cur- > next; free (cur); cur = next;} return } print linked list / / two-way linked list print void ListPrint (ListNode* pHead) {/ / assert that the incoming pointer is not NULL assert (pHead); / / create an addressing pointer ListNode* cur = pHead- > next / / cycle through the linked list while (cur! = pHead) {/ / print data printf ("% d->", cur- > data); / / find the next node cur = cur- > next;} printf ("NULL\ n"); return } tail-inserted list / / Bidirectional linked list insert void ListPushBack (ListNode* pHead, LTDataType x) {/ / assert that the incoming pointer is not NULL assert (pHead); / / create the node ListNode* newnode = BuyListNode (x); / / find the tail node ListNode* tail=pHead- > prev; tail- > next = newnode; newnode- > prev = tail; pHead- > prev = newnode; newnode- > next = pHead } tail delete linked list

Record the address of the previous node before deletion

/ / two-way linked list tail deletion void ListPopBack (ListNode* pHead) {/ / asserts that the incoming pointer is not NULL assert (pHead); / / if only the Sentinel header node is left, if (pHead- > prev = = pHead) return; / / record the tail node and its previous node ListNode* tail = pHead- > prev; ListNode* tailprev = tail- > prev / / release the tail node free (tail); / / construct the relationship between the front node of the tail node and the Sentinel head node tailprev- > next = pHead; pHead- > prev = tailprev; return;} header insertion list

Record the next node of the Sentinel head node before inserting the head.

/ / two-way chain header insert void ListPushFront (ListNode* pHead, LTDataType x) {/ / assert that the incoming pointer is not NULL assert (pHead); / / create a node ListNode* newnode = BuyListNode (x); / / record the next node of the Sentinel header node ListNode* next = pHead- > next; / / build the relationship between nodes pHead- > next = newnode Newnode- > prev = pHead; newnode- > next = next; next- > prev = newnode; return;} header delete list / / two-way link header delete void ListPopFront (ListNode* pHead) {/ / assert that the incoming pointer is not NULL assert (pHead); / / if only the Sentinel head node is left if (pHead- > next = = pHead) return / / record the next node of Sentinel head node and its next node ListNode* next = pHead- > next; ListNode* nextNext = next- > next; / / release node free (next); pHead- > next = nextNext; nextNext- > prev = pHead; return } lookup linked list / / two-way linked list lookup ListNode* ListFind (ListNode* pHead, LTDataType x) {/ / asserts that the incoming pointer is not NULL assert (pHead); / / create an addressing pointer ListNode* cur = pHead- > next While (cur! = pHead) {/ / compare data if (cur- > data = = x) return cur; / / find the next node cur = cur- > next;} / / return NULL return NULL if not found } deletion of the pos position of the linked list void ListErase (ListNode* pos) {assert (pos); ListNode* prev = pos- > prev; ListNode* next = pos- > next; free (pos); prev- > next = next; next- > prev = prev; return;} at this point, the study on "how to implement the C++-led two-way circular linked list" is over. I hope to be able to solve your 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.