数据结构与算法之链表详解
链表是一种常见的基础数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表与数组相比，具有动态分配内存、插入和删除操作效率高等特点。本文将围绕链表的基础概念，详细介绍单链表、双向链表和循环链表。
单链表
基本概念
单链表是最简单的链表形式，每个节点包含数据和指向下一个节点的指针。单链表不支持随机访问，只能从头节点开始遍历。
代码实现
以下是一个单链表的简单实现：
python
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
class SingleLinkedList:
def __init__(self):
self.head = None
def append(self, value):
if not self.head:
self.head = ListNode(value)
else:
current = self.head
while current.next:
current = current.next
current.next = ListNode(value)
def display(self):
current = self.head
while current:
print(current.value, end=' ')
current = current.next
print()
测试单链表
sll = SingleLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()
操作
- `append(value)`: 在链表末尾添加一个新节点。
- `display()`: 打印链表中的所有节点值。
双向链表
基本概念
双向链表是单链表的扩展，每个节点包含数据和指向下一个节点以及前一个节点的指针。双向链表支持从头节点或尾节点开始遍历。
代码实现
以下是一个双向链表的简单实现：
python
class DoublyListNode:
def __init__(self, value=0, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, value):
new_node = DoublyListNode(value)
if not self.head:
self.head = self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def display(self):
current = self.head
while current:
print(current.value, end=' ')
current = current.next
print()
测试双向链表
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()
操作
- `append(value)`: 在链表末尾添加一个新节点。
- `display()`: 打印链表中的所有节点值。
循环链表
基本概念
循环链表是单链表和双向链表的进一步扩展，每个节点的指针指向下一个节点，最后一个节点的指针指向头节点，形成一个环。
代码实现
以下是一个循环链表的简单实现：
python
class CircularListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, value):
new_node = CircularListNode(value)
if not self.head:
self.head = new_node
self.head.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def display(self):
current = self.head
while True:
print(current.value, end=' ')
current = current.next
if current == self.head:
break
print()
测试循环链表
circular_list = CircularLinkedList()
circular_list.append(1)
circular_list.append(2)
circular_list.append(3)
circular_list.display()
操作
- `append(value)`: 在链表末尾添加一个新节点。
- `display()`: 打印链表中的所有节点值。
总结
本文详细介绍了单链表、双向链表和循环链表的基本概念、代码实现和操作。链表是一种灵活且高效的数据结构，在许多实际应用中都有广泛的应用。通过学习链表，我们可以更好地理解数据结构和算法，为后续的学习打下坚实的基础。
Comments NOTHING