双链表的创建，插入，删除_c语言创建链表并输入数据资源-CSDN下载

共3个文件

vcproj：1个

user：1个

cpp：1个

5星 · 超过95%的资源需积分: 9 189 浏览量 2012-08-28 19:04:19 上传评论 1 收藏 3KB RAR 举报

双链表是一种常见的数据结构，它扩展了单链表的概念，每个节点不仅包含数据，还包含两个指针，一个指向前一个节点（prev），另一个指向后一个节点（next）。这种结构使得在链表中的双向移动变得更为便捷。下面将详细讨论双链表的创建、插入和删除操作。 **创建双链表** 创建一个双链表通常涉及到初始化一个头节点，这个头节点可以是空的，也可以包含数据。如果初始为空，那么头节点的前一个指针和后一个指针都应指向自身，表示一个空链表。在C++中，创建一个空链表的示例代码如下： ```cpp struct Node { int data; Node* prev; Node* next; }; Node* createEmptyLinkedList() { Node* head = new Node(); head->prev = head; head->next = head; return head; } ``` **插入节点** 插入节点分为在表头、表中和表尾进行。在表头插入时，新节点的next指针应指向原头节点，而原头节点的prev指针应指向新节点。在表尾插入时，需要找到最后一个节点（其next指针指向头节点），然后更新它的next指针和新节点的prev指针。在表中插入时，需要找到插入位置的前一个节点，并更新前后节点的指针。例如，在表尾插入节点的C++实现： ```cpp void insertAtTail(Node* head, int value) { Node* newNode = new Node(); newNode->data = value; newNode->prev = head->prev; newNode->next = head; head->prev->next = newNode; head->prev = newNode; } ``` **删除节点** 删除节点操作则需要考虑被删除节点的前一个和后一个节点。根据要删除的节点位置，更新这些节点的指针。删除表头节点时，需要更新头节点的prev指针；删除表尾节点时，需要找到前一个节点并更新其next指针；删除中间节点时，需要更新前后节点的指针。以下是在表头删除节点的C++代码示例： ```cpp void deleteFromHead(Node*& head) { if (head == head->next) { // 如果链表只有一个节点 delete head; head = nullptr; } else { Node* temp = head; head = head->next; head->prev = temp->prev; delete temp; } } ``` 在处理双链表时，需要注意边界条件，如空链表的操作。当链表为空时，插入和删除操作都需要特别处理，以免出现未定义的行为。同时，由于双向链表的特性，插入和删除操作的时间复杂度通常为O(1)，因为不需要遍历整个链表来找到插入或删除的位置。双链表在许多实际应用中都有所体现，如实现LRU缓存策略、表示复杂的数据关系等。理解和熟练掌握双链表的创建、插入和删除操作是编程基础的重要组成部分，对于提升算法和数据结构能力非常有帮助。通过实践和编程练习，可以更深入地理解这些概念。

资源推荐

资源详情

资源评论

收起资源包目录

DoubleLinkList.rar （3个子文件）

DoubleLinkList

DoubleLinkList.vcproj.PC-201207101739.Administrator.user 1KB

DoubleLinkList.vcproj 4KB

main.cpp 4KB

#include <iostream> using namespace std; typedef struct Node{ int data; Node *pLast; Node *pNext; }lnode;//lnode is another name of the struct; struct Node node1 = lnode node1 lnode *CreateDoubleLinkList(); void PrintDoubleLinkList(lnode *phead); int GetLengthDoubleLinkList(lnode *phead); lnode *InsertDoubleLinkList(lnode *phead, int postion, int InsertData); lnode *DeleteDoubleLinkList(lnode *phead, int postion); int main() { lnode *head = (lnode *)malloc(sizeof(lnode)); head = CreateDoubleLinkList(); int len = GetLengthDoubleLinkList(head); cout<<"Please input the data you want to insert, and the place: "; int InsertData, Postion; cin>>InsertData>>Postion; head = InsertDoubleLinkList(head, Postion, InsertData); cout<<"Please input the position of node you want to delete: "; int DeletePostion; cin>>DeletePostion; head = DeleteDoubleLinkList(head, DeletePostion); return 0; } lnode *CreateDoubleLinkList() { lnode *phead = (lnode *)malloc(sizeof(lnode)); cout<<"Please input the data in the new list with key 'ENTER' or 'BLANK' as an interval, and end with '0': "; int tempData; cin>>tempData; if (tempData == 0)//an empty list, have no node { free(phead); cout<<"The list is NULL!"<<endl; return NULL; } phead->data = tempData;//the list have one node at least phead->pLast = NULL; phead->pNext = NULL; cin>>tempData; lnode *p = phead; while(tempData != 0) { lnode *tempNode = (lnode *)malloc(sizeof(lnode)); tempNode->data = tempData; p->pNext = tempNode; tempNode->pLast = p; tempNode->pNext = NULL; p = tempNode; cin>>tempData; } PrintDoubleLinkList(phead); return phead; } void PrintDoubleLinkList(lnode *phead) { cout<<"The list is: "; while(phead) { cout<<phead->data<<" "; phead = phead->pNext; } cout<<endl; } int GetLengthDoubleLinkList(lnode *phead) { int len = 0; while(phead) { len++; phead = phead->pNext; } cout<<"The length of the list is : "<<len<<endl; return len; } lnode *InsertDoubleLinkList(lnode *phead, int postion, int InsertData) { cout<<"Before Insert, "; int len = GetLengthDoubleLinkList(phead); if (phead == NULL)//the original list is NULL { lnode *tempNode = (lnode *)malloc(sizeof(lnode)); tempNode->data = InsertData; tempNode->pLast = NULL; tempNode->pNext = NULL; phead = tempNode; cout<<"After Insert, "; len = GetLengthDoubleLinkList(phead); PrintDoubleLinkList(phead); return tempNode; } if (len < postion) { cout<<"The list is too short to be inserted!"<<endl; } else//position <= length { lnode *tempNode = (lnode *)malloc(sizeof(lnode)); tempNode->data = InsertData; lnode *p = phead; lnode *q; if (postion == 0)//insert before the head { tempNode->pLast = NULL; tempNode->pNext = p; p->pLast = tempNode; phead = tempNode; } else { while(postion > 1) { postion--; p = p->pNext; } q = p->pNext;//the node will insert between p and q if (q == NULL)//insert after the tail { p->pNext = tempNode; tempNode->pLast = p; tempNode->pNext = NULL; } else { tempNode->pLast = p; tempNode->pNext = q; p->pNext = tempNode; q->pLast = tempNode; } } } cout<<"After Insert, "; len = GetLengthDoubleLinkList(phead); PrintDoubleLinkList(phead); return phead; } lnode *DeleteDoubleLinkList(lnode *phead, int postion) { if (phead == NULL) { cout<<"The list is NULL, so the deleting can not be operated!"<<endl; } else { cout<<"Before delete, "; int len = GetLengthDoubleLinkList(phead); if (len < postion) { cout<<"The list is shorted than the specified position!"<<endl; } else { lnode *p; p = phead; if (postion == 1)//delete the head node { phead = phead->pNext; phead->pLast = NULL; free(p); } else { while(postion > 1) { postion--; p = p->pNext; } lnode *q = p->pNext; lnode *tempNode = p; if (q == NULL)//delete the tail { p = p->pLast; p->pNext = NULL; free(tempNode); tempNode = NULL; } else//delete the node between p and q { p = p->pLast; p->pNext = q; q->pLast = p; free(tempNode); tempNode = NULL; } } } } cout<<"After delete, "; int len = GetLengthDoubleLinkList(phead); PrintDoubleLinkList(phead); return phead; }

评论收藏

内容反馈