别再死记硬背了！用Python/C++手搓顺序表和链表，5分钟搞懂数据结构核心
·
别再死记硬背了！用Python/C++手搓顺序表和链表，5分钟搞懂数据结构核心
当你第一次接触数据结构时，是否曾被顺序表和链表的区别搞得晕头转向？面试官问"删除尾结点时间复杂度"时，你是否只能机械背诵答案？本文将带你用代码亲手实现这两种基础数据结构，在动手实践中建立深刻理解。
1. 顺序表：连续存储的利与弊
顺序表的核心特点是元素在内存中的物理存储顺序与逻辑顺序一致。这种连续存储的特性带来了独特的优势和局限。
1.1 Python实现动态顺序表
class SequentialList:
def __init__(self):
self._capacity = 10 # 初始容量
self._size = 0
self._data = [None] * self._capacity
def __resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data
self._capacity = new_capacity
def insert(self, index, value):
if index < 0 or index > self._size:
raise IndexError("Invalid index")
if self._size == self._capacity:
self.__resize(self._capacity * 2)
for i in range(self._size, index, -1):
self._data[i] = self._data[i-1]
self._data[index] = value
self._size += 1
def delete(self, index):
if index < 0 or index >= self._size:
raise IndexError("Invalid index")
for i in range(index, self._size-1):
self._data[i] = self._data[i+1]
self._size -= 1
if self._size < self._capacity // 4:
self.__resize(self._capacity // 2)
关键观察：插入/删除操作需要移动元素，平均时间复杂度O(n)；但随机访问只需O(1)
1.2 C++实现静态顺序表
#define MAX_SIZE 100
template<typename T>
class StaticSeqList {
private:
T data[MAX_SIZE];
int length;
public:
StaticSeqList() : length(0) {}
bool insert(int index, T value) {
if(index < 0 || index > length || length == MAX_SIZE)
return false;
for(int i = length; i > index; --i)
data[i] = data[i-1];
data[index] = value;
length++;
return true;
}
bool remove(int index) {
if(index < 0 || index >= length)
return false;
for(int i = index; i < length-1; ++i)
data[i] = data[i+1];
length--;
return true;
}
};
顺序表的优势场景：
- 高频随机访问 ：如需要频繁按索引获取元素
- 缓存友好 ：连续内存布局提高缓存命中率
- 空间效率 ：不需要额外存储指针
2. 链表：灵活的非连续存储
链表通过指针将分散的内存块连接起来，每个节点包含数据域和指针域。我们重点实现单链表和双向链表。
2.1 Python实现单链表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def insert(self, index, value):
if index < 0 or index > self.size:
raise IndexError("Invalid index")
new_node = ListNode(value)
if index == 0:
new_node.next = self.head
self.head = new_node
else:
prev = self.head
for _ in range(index-1):
prev = prev.next
new_node.next = prev.next
prev.next = new_node
self.size += 1
def delete(self, index):
if index < 0 or index >= self.size:
raise IndexError("Invalid index")
if index == 0:
self.head = self.head.next
else:
prev = self.head
for _ in range(index-1):
prev = prev.next
prev.next = prev.next.next
self.size -= 1
2.2 C++实现双向链表
template<typename T>
struct DListNode {
T data;
DListNode* prev;
DListNode* next;
DListNode(T val) : data(val), prev(nullptr), next(nullptr) {}
};
template<typename T>
class DoublyLinkedList {
private:
DListNode<T>* head;
DListNode<T>* tail;
int size;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
void insert(int index, T value) {
if(index < 0 || index > size) return;
DListNode<T>* newNode = new DListNode<T>(value);
if(size == 0) {
head = tail = newNode;
} else if(index == 0) {
newNode->next = head;
head->prev = newNode;
head = newNode;
} else if(index == size) {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
} else {
DListNode<T>* curr = head;
for(int i = 0; i < index; ++i)
curr = curr->next;
newNode->prev = curr->prev;
newNode->next = curr;
curr->prev->next = newNode;
curr->prev = newNode;
}
size++;
}
void remove(int index) {
if(index < 0 || index >= size) return;
DListNode<T>* toDelete;
if(index == 0) {
toDelete = head;
head = head->next;
if(head) head->prev = nullptr;
else tail = nullptr;
} else if(index == size-1) {
toDelete = tail;
tail = tail->prev;
tail->next = nullptr;
} else {
DListNode<T>* curr = head;
for(int i = 0; i < index; ++i)
curr = curr->next;
toDelete = curr;
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
}
delete toDelete;
size--;
}
};
链表的核心特点：
- 动态大小 ：无需预先分配固定空间
- 高效插入/删除 ：只需修改指针，无需移动元素
- 内存分散 ：节点可以分布在内存任意位置
3. 时间复杂度对比实战
通过具体操作对比两种结构的时间复杂度差异：
| 操作 | 顺序表 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | O(1) | O(1) |
| 中间插入 | O(n) | O(n) |
| 头部删除 | O(n) | O(1) |
| 尾部删除 | O(1) | O(n) |
| 中间删除 | O(n) | O(n) |
注意：链表尾部删除在单链表中需要O(n)时间遍历找到前驱节点，但如果有尾指针可以优化到O(1)
4. 面试高频问题解析
4.1 为什么链表删除尾结点需要O(n)时间？
单链表要删除尾结点，必须从头遍历找到倒数第二个节点才能修改其next指针。这是单链表的结构特性决定的。
def delete_tail(self):
if not self.head:
return
if not self.head.next:
self.head = None
return
current = self.head
while current.next.next:
current = current.next
current.next = None
4.2 如何优化链表尾部操作？
两种常见优化方案：
- 维护尾指针 ：
class LinkedListWithTail:
def __init__(self):
self.head = None
self.tail = None
def append(self, value):
new_node = ListNode(value)
if not self.head:
self.head = self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
- 使用双向链表 ：
// 双向链表的尾部删除
void pop_back() {
if(!tail) return;
if(tail == head) {
delete tail;
head = tail = nullptr;
} else {
DListNode<T>* temp = tail;
tail = tail->prev;
tail->next = nullptr;
delete temp;
}
size--;
}
4.3 顺序表扩容的代价
顺序表扩容需要申请新内存并复制所有元素，虽然均摊时间复杂度仍是O(1)，但实际应用中仍需注意：
def __resize(self, new_capacity):
print(f"Resizing from {self._capacity} to {new_capacity}")
# 其余代码不变...
典型扩容策略：
- 倍增策略 ：容量翻倍（Python list采用）
- 固定增量 ：每次增加固定大小
- 混合策略 ：小表时倍增，大表后固定增量
5. 工程实践中的选择建议
实际开发中如何选择数据结构？以下是一些经验法则：
选择顺序表当 ：
- 需要频繁随机访问元素
- 已知或能预估元素数量上限
- 内存使用效率是关键考量
- 需要利用CPU缓存局部性优化
选择链表当 ：
- 需要频繁在头部/中间插入删除
- 元素数量变化大且难以预估
- 需要实现先进先出(FIFO)队列
- 内存碎片化是主要顾虑
高级变体选择 ：
- 动态数组 ：Python list、C++ vector、Java ArrayList
- 跳表 ：Redis有序集合的实现
- 未排序链表+哈希表 ：实现O(1)插入删除和查找
更多推荐
13
0- 0
已为社区贡献44条内容
所有评论(0)