数据结构--链表

链表

有种数据结构和火车非常相似，那就是链表啦。在链表里，我们叫火车头为表头，每节车厢就是链表的元素，车厢里载的人和物就是元素的数据域，连接车厢的部件就是元素的指针。从火车的结构我们可以发现链表的一个特点，元素之间前后依赖，串联而成。

还有，我们可以发现，链表的元素不能随机访问。想象下，在高速运行的火车上，如果我们想到达某个车厢，是不是只能挨个车厢走过去，而不能直接走到目标车厢。

另外，除了火车头，每节车厢前面只链接一节车厢；除了最后的车厢，每节车厢后面也只链接一节车厢，这也是链表的特点，元素前面和后面不会出现多个元素相连的情况。

元素相互依赖，串联而成（除了火车头，每节车厢都只链接到前一节车厢）链表只有一个表头（火车只有一个火车头）元素不能随机访问（不能随机到达某节车厢）

---

加入新车厢

#include<iostream> using namespace std; class Node { public: int data; Node* next; Node(int _data) { data = _data; next = NULL; } }; class LinkList { private: Node* head; public: LinkList() { head = NULL; } void insert(Node *node,int index){ if(head==NULL){ head = node; return; } if(index==0){ node->next=head; head = node; return; } Node *current_node=head; int count = 0; while(current_node->next !=NULL && count<index-1){ current_node = current_node->next ; count++; } if(count == index-1){ node ->next = current_node->next; current_node-> next = node; } } }; int main() { LinkList linklist; for(int i=1;i<=10;i++){ Node *node = new Node(i); linklist.insert(node,i-1); } return 0; }

---

从车头走到车尾

#include<iostream> using namespace std; class Node { public: int data; Node* next; Node(int _data) { data = _data; next = NULL; } }; class LinkList { private: Node* head; public: LinkList() { head = NULL; } void insert(Node *node, int index) { if (head == NULL) { head = node; return; } if (index == 0) { node->next = head; head = node; return; } Node *current_node = head; int count = 0; while (current_node->next != NULL && count < index - 1) { current_node = current_node->next; count++; } if (count == index - 1) { node->next = current_node->next; current_node->next = node; } } void output(){ if(head==NULL){ return; } Node *current_node=head; while(current_node!=NULL){ cout<<current_node->data<<" "; current_node = current_node->next; } cout<<endl; } }; int main() { LinkList linklist; for (int i = 1; i <= 10; i++) { Node *node = new Node(i); linklist.insert(node, i - 1); } linklist.output(); return 0; }