Python单向链表和双向链表原理与用法实例详解

简介

链表是数据结构中的一种基本数据结构，由一系列节点（元素）组成，每个节点包含数据域和指针，指针指向下一个节点或前后节点。链表可以分为单向链表和双向链表。单向链表只保存对下一个节点的引用，而双向链表除了保存对下一个节点的引用外，还保存对前一个节点的引用。

单向链表

单向链表是最简单的链表类型，每个节点包含数据和指向下一个节点的指针，最后一个节点的指针指向NULL。

创建单向链表

创建单向链表需要定义一个Node类，该类包含一个数据域和指向下一个节点的指针。

class Node:
   def __init__(self, data=None):
      self.data = data
      self.next = None

然后可以定义一个LinkedList类，该类包含一个头节点。

class LinkedList:
   def __init__(self):
      self.head = None

可以定义添加、删除节点以及遍历链表的方法。

class LinkedList:
   # ...

   def add_node(self, data):
      new_node = Node(data)
      if self.head is None:
         self.head = new_node
         return

      last = self.head
      while last.next:
         last = last.next

      last.next = new_node


   def remove_node(self, key):
      cur_node = self.head
      if cur_node and cur_node.data == key:
          self.head = cur_node.next
          cur_node = None
          return

      prev = None
      while cur_node and cur_node.data != key:
          prev = cur_node
          cur_node = cur_node.next

      if cur_node is None:
          return

      prev.next = cur_node.next
      cur_node = None


   def print_list(self):
      cur_node = self.head
      while cur_node:
          print(cur_node.data)
          cur_node = cur_node.next

示例1：创建单向链表并添加、删除节点

# Create List
linkedList = LinkedList()
linkedList.add_node(1)
linkedList.add_node(2)
linkedList.add_node(3)
linkedList.add_node(4)

# Print List
print("Original List:")
linkedList.print_list()

# Remove Node
linkedList.remove_node(2)

# Print List
print("Updated List:")
linkedList.print_list()

输出：

Original List:
1
2
3
4
Updated List:
1
3
4

双向链表

双向链表除了保存对下一个节点的引用外，还保存对前一个节点的引用。每个节点包含数据、指向下一个节点的指针以及指向前一个节点的指针，第一个节点的指向前一个节点的指针指向NULL，最后一个节点的指向下一个节点的指针指向NULL。

创建双向链表

创建双向链表需要定义一个Node类，该类包含一个数据域、指向前一个节点的指针以及指向下一个节点的指针。

class Node:
   def __init__(self, data=None, prev=None, next=None):
      self.data = data
      self.prev = prev
      self.next = next

然后可以定义一个DoublyLinkedList类，该类包含一个头节点和一个尾节点。

class DoublyLinkedList:
   def __init__(self):
      self.head = None
      self.tail = None

可以定义添加、删除节点以及遍历链表的方法。

class DoublyLinkedList:
   # ...

   def add_node(self, data):
      new_node = Node(data)
      if self.head is None:
         self.head = new_node
         self.tail = new_node
         return

      new_node.prev = self.tail
      self.tail.next = new_node
      self.tail = new_node


   def remove_node(self, key):
      cur_node = self.head
      if cur_node and cur_node.data == key:
         if cur_node.next is None:
            cur_node = None
            self.head = None
            self.tail = None
            return

         next_node = cur_node.next
         next_node.prev = None
         cur_node.next = None
         cur_node = None
         self.head = next_node
         return

      while cur_node and cur_node.data != key:
         cur_node = cur_node.next

      if cur_node is None:
         return

      if cur_node.next is None:
         cur_node.prev.next = None
         self.tail = cur_node.prev
         return

      next_node = cur_node.next
      prev_node = cur_node.prev
      prev_node.next = next_node
      next_node.prev = prev_node
      cur_node.next = None
      cur_node.prev = None
      cur_node = None


   def print_list(self):
      cur_node = self.head
      while cur_node:
          print(cur_node.data)
          cur_node = cur_node.next

示例2：创建双向链表并添加、删除节点

# Create List
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.add_node(1)
doublyLinkedList.add_node(2)
doublyLinkedList.add_node(3)
doublyLinkedList.add_node(4)

# Print List
print("Original List:")
doublyLinkedList.print_list()

# Remove Node
doublyLinkedList.remove_node(2)

# Print List
print("Updated List:")
doublyLinkedList.print_list()

输出：

Original List:
1
2
3
4
Updated List:
1
3
4