数据结构

链表是一种线性数据结构，它通过节点相连来存储数据.

什么是链表？

链表是一种线性数据结构，其中每个元素（称为节点）包含两个部分：

  1. 数据域 (Data) ：存储实际的数据。
  2. 指针域 (Pointer/Link) ：指向下一个节点的引用。对于单向链表来说，这个指针通常称为“next”。

链表的类型

1. 单向链表 (Singly Linked List)

  • 每个节点只有一个指针，指向下一个节点。

  • 特点：

    • 插入和删除操作较简单，因为只需要修改一个指针。
    • 访问特定元素的时间复杂度为O(n)，因为需要从头开始遍历。

2. 双向链表 (Doubly Linked List)

  • 每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。

  • 特点：

    • 插入和删除操作较复杂，因为需要修改两个指针。
    • 访问特定元素的时间复杂度为O(n)，但可以双向遍历。

3. 循环链表 (Circular Linked List)

  • 链表的最后一个节点指向第一个节点，形成一个环。

  • 特点：

    • 在某些情况下（如循环队列）非常有用。

链表的操作

插入操作

  1. 在头部插入：将新节点的next指针指向当前头节点，然后更新头节点。
  2. 在尾部插入：遍历到链表的最后一个节点，将其next指针指向新节点。
  3. 在指定位置插入：找到目标节点，并调整指针以插入新节点。

删除操作

  1. 删除头部节点：将头节点更新为下一个节点。
  2. 删除尾部节点：遍历到倒数第二个节点，将其next指针设为null。
  3. 删除指定节点：找到目标节点，并调整前一个节点的next指针。

遍历操作

  • 从头节点开始，依次访问每个节点，直到链表结束（即遇到null）。

实现单向链表

下面是一个简单的Python实现：

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

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

    def is_empty(self):
        return self.head is None

    def append(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, key):
        if not self.is_empty():
            if self.head.data == key:
                self.head = self.head.next
                return
            current = self.head
            while current.next and current.next.data != key:
                current = current.next
            if current.next:
                current.next = current.next.next

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 示例使用
llist = SinglyLinkedList()
llist.append(1)
llist.append(2)
llist.prepend(0)
llist.display()  # 输出: 0 -> 1 -> 2 -> None

llist.delete(1)
llist.display()  # 输出: 0 -> 2 -> None

print(llist.search(2))  # 输出: True

发表评论