1 链表概念
链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思),链表的入口节点称为链表的头结点也就是head。

2 链表类型
1. 单链表
如上图所示,只有一个方向。
2. 双链表
单链表中的指针域只能指向节点的下一个节点。双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点,双链表既可以向前查询也可以向后查询。

3. 循环链表
循环链表,就是链表首尾相连。
链表43 链表的定义
1. C/C++定义链表节点方式
- 节点定义
1 2 3 4 5 6
| // 单链表 struct ListNode { int val; // 节点上存储的元素 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数 };
|
- 创建链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class LinkedList { private: ListNode *head;
public: LinkedList() : head(nullptr) {} ~LinkedList() { ListNode *current = head; while (current != nullptr) { ListNode *next = current->next; delete current; current = next; } head = nullptr; }
void append(int data) { ListNode *newNode = new ListNode(data); if (head == nullptr) { head = newNode; } else { ListNode *current = head; while (current->next != nullptr) { current = current->next; } current->next = newNode; } }
void print() const { ListNode *current = head; while (current != nullptr) { std::cout << current->data << " "; current = current->next; } std::cout << std::endl; } };
|
2. Python定义链表节点方式
- 节点定义:首先定义一个节点类,其中包含数据和指向下一个节点的引用。
1 2 3 4
| class ListNode: def __init__(self, data): self.data = data self.next = None
|
- 链表定义:然后可以定义一个链表类,其中包含对链表头节点的引用,以及添加、删除和打印等操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| class LinkedList: def __init__(self): self.head = None
def append(self, data): if not self.head: self.head = ListNode(data) else: current = self.head while current.next: current = current.next current.next = ListNode(data)
def print_list(self): current = self.head while current: print(current.data) current = current.next
ll = LinkedList() ll.append(1) ll.append(2) ll.append(3)
ll.print_list()
|
4 链表的操作
1. 删除节点

只要将C节点的next指针 指向E节点就可以了。在C++里最好是再手动释放这个D节点,释放这块内存。其他语言例如Java、Python,就有自己的内存回收机制,就不用自己手动释放了。
- C++ 删除节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| void deleteNode(int key) { ListNode *current = head; ListNode *previous = nullptr;
while (current != nullptr && current->data != key) { previous = current; current = current->next; }
if (current != nullptr) { if (previous == nullptr) { head = current->next; } else { previous->next = current->next; } delete current; } }
|
- Python 删除节点
1 2 3 4 5 6 7 8 9 10 11
| ll = LinkedList() ll.append(1) ll.append(2) ll.append(3)
print("原始链表:") ll.print_list()
ll.delete(2) print("删除节点 2 后的链表:") ll.print_list()
|
2. 添加节点

链表的增添和删除都是O(1)操作,也不会影响到其他节点。但是要注意,要是删除第五个节点,需要从头节点查找到第四个节点通过next指针进行删除操作,查找的时间复杂度是O(n)。操作在上面的定义链表中。