算法训练之 -- 链表理论基础

1 链表概念

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

链表1

2 链表类型

1. 单链表

  如上图所示,只有一个方向。

2. 双链表

  单链表中的指针域只能指向节点的下一个节点。双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点,双链表既可以向前查询也可以向后查询。

链表2

3. 循环链表

  循环链表,就是链表首尾相连。

链表4

3 链表的定义

1. C/C++定义链表节点方式

  1. 节点定义
1
2
3
4
5
6
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
  1. 创建链表
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. 节点定义:首先定义一个节点类,其中包含数据和指向下一个节点的引用。
1
2
3
4
class ListNode:
def __init__(self, data):
self.data = data
self.next = None
  1. 链表定义:然后可以定义一个链表类,其中包含对链表头节点的引用,以及添加、删除和打印等操作。
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,就有自己的内存回收机制,就不用自己手动释放了。

  1. 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;
}
}
  1. 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)。操作在上面的定义链表中。


算法训练之 -- 链表理论基础
http://seulqxq.top/posts/24066/
作者
SeulQxQ
发布于
2024年1月10日
许可协议