链表是一种常见的数据结构，用于存储一系列的元素。链表由多个节点组成，每个节点包含两部分：数据和指向下一个节点的指针。它与数组相比具有动态性和灵活性的特点，可以根据需要插入、删除和修改节点。
## 单链表
单链表是最简单的链表形式，每个节点只包含数据和指向下一个节点的指针。链表的头节点可用于访问链表的第一个元素。
下面是一个简单的单链表的实现代码：
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def display(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
```
在上面的代码中，Node类表示链表的节点，包含数据和指向下一个节点的指针。LinkedList类表示链表本身，包含头节点和一些操作方法。其中，append方法用于在链表末尾追加一个节点，display方法用于打印链表中的所有元素。
## 双向链表
双向链表是一种扩展的链表形式，节点除了包含数据和指向下一个节点的指针外，还包含指向上一个节点的指针。通过这种方式，双向链表可以实现从头到尾和从尾到头访问链表。
下面是一个简单的双向链表的实现代码：
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def display_forward(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
def display_backward(self):
current = self.head
if current is None:
return
while current.next:
current = current.next
while current:
print(current.data, end=" -> ")
current = current.prev
print("None")
```
在上面的代码中，Node类的定义与单链表相同，但新增了一个prev属性用于指向上一个节点。DoublyLinkedList类的操作方法与单链表类似，但新增了一个display_backward方法，用于逆序打印链表中的所有元素。
链表是一种重要的数据结构，在实际编程中经常用到。通过学习链表的实现代码，我们可以更好地理解链表的原理和操作方法，为解决实际问题提供了一个有力的工具。
