链表(Linked List)

链表是一种常见的数据结构,它由一系列节点(Node)组成,每个节点包含数据和指向下一个节点的引用(指针)。链表的主要优点是插入和删除操作的时间复杂度为O(1),但访问特定元素的时间复杂度为O(n)。

单链表(Singly Linked List)

单链表是最简单的链表形式,每个节点只有一个指向下一个节点的引用。

节点类(Node Class)

首先,我们需要定义一个节点类,每个节点包含数据和指向下一个节点的引用。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
链表类(Linked List Class)

接下来,我们定义一个链表类,包含链表的头节点和一些基本操作。

class LinkedList:
    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):
        current = self.head
        previous = None
        while current and current.data != key:
            previous = current
            current = current.next
        if current is None:
            return
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next

    def search(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        return current is not None

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

我们可以创建一个链表实例并进行一些操作。

# 创建链表实例
llist = LinkedList()

# 添加元素
llist.append(1)
llist.append(2)
llist.append(3)

# 显示链表
llist.display()  # 输出: 1 -> 2 -> 3 -> None

# 在头部添加元素
llist.prepend(0)
llist.display()  # 输出: 0 -> 1 -> 2 -> 3 -> None

# 删除元素
llist.delete(2)
llist.display()  # 输出: 0 -> 1 -> 3 -> None

# 搜索元素
print(llist.search(1))  # 输出: True
print(llist.search(2))  # 输出: False

不用类的方法实现链表

虽然使用类的方法实现链表更加面向对象和模块化,但我们也可以不使用类的方法来实现链表。这种方法通常用于简单的脚本或小规模的数据处理。

实现单链表

我们可以使用函数和字典来实现链表。

def create_node(data):
    return {"data": data, "next": None}

def append_node(head, data):
    new_node = create_node(data)
    if head is None:
        return new_node
    current = head
    while current["next"]:
        current = current["next"]
    current["next"] = new_node
    return head

def prepend_node(head, data):
    new_node = create_node(data)
    new_node["next"] = head
    return new_node

def delete_node(head, key):
    current = head
    previous = None
    while current and current["data"] != key:
        previous = current
        current = current["next"]
    if current is None:
        return head
    if previous is None:
        head = current["next"]
    else:
        previous["next"] = current["next"]
    return head

def search_node(head, key):
    current = head
    while current and current["data"] != key:
        current = current["next"]
    return current is not None

def display_list(head):
    current = head
    while current:
        print(current["data"], end=" -> ")
        current = current["next"]
    print("None")
使用函数实现链表

我们可以使用这些函数来创建和操作链表。

# 创建链表
head = None

# 添加元素
head = append_node(head, 1)
head = append_node(head, 2)
head = append_node(head, 3)

# 显示链表
display_list(head)  # 输出: 1 -> 2 -> 3 -> None

# 在头部添加元素
head = prepend_node(head, 0)
display_list(head)  # 输出: 0 -> 1 -> 2 -> 3 -> None

# 删除元素
head = delete_node(head, 2)
display_list(head)  # 输出: 0 -> 1 -> 3 -> None

# 搜索元素
print(search_node(head, 1))  # 输出: True
print(search_node(head, 2))  # 输出: False

具体讲解

类的方法实现链表

Node类
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
  • __init__方法:这是Node类的构造方法,用于初始化节点的数据和指向下一个节点的引用。
LinkedList类
class LinkedList:
    def __init__(self):
        self.head = None
  • __init__方法:这是LinkedList类的构造方法,用于初始化链表的头节点。
    def is_empty(self):
        return self.head is None
  • is_empty方法:这个方法用于检查链表是否为空。如果头节点为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
  • append方法:这个方法用于在链表的末尾添加一个新节点。如果链表为空,则新节点成为头节点;否则,遍历链表直到找到最后一个节点,然后将新节点添加到其后面。
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
  • prepend方法:这个方法用于在链表的头部添加一个新节点。新节点的next指针指向当前的头节点,然后新节点成为新的头节点。
    def delete(self, key):
        current = self.head
        previous = None
        while current and current.data != key:
            previous = current
            current = current.next
        if current is None:
            return
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next
  • delete方法:这个方法用于删除链表中第一个值为key的节点。遍历链表,找到值为key的节点,然后将其从链表中移除。如果节点是头节点,则更新头节点;否则,更新前一个节点的next指针。
    def search(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        return current is not None
  • search方法:这个方法用于检查链表中是否存在值为key的节点。遍历链表,找到值为key的节点,如果找到则返回True,否则返回False。
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")
  • display方法:这个方法用于显示链表中的所有节点。遍历链表,打印每个节点的数据,最后打印"None"表示链表结束。

不用类的方法实现链表

创建节点
def create_node(data):
    return {"data": data, "next": None}
  • create_node函数:这个函数用于创建一个新节点,返回一个包含数据和next指针的字典。
添加节点
def append_node(head, data):
    new_node = create_node(data)
    if head is None:
        return new_node
    current = head
    while current["next"]:
        current = current["next"]
    current["next"] = new_node
    return head
  • append_node函数:这个函数用于在链表的末尾添加一个新节点。如果链表为空,则新节点成为头节点;否则,遍历链表直到找到最后一个节点,然后将新节点添加到其后面。
def prepend_node(head, data):
    new_node = create_node(data)
    new_node["next"] = head
    return new_node
  • prepend_node函数:这个函数用于在链表的头部添加一个新节点。新节点的next指针指向当前的头节点,然后新节点成为新的头节点。
删除节点
def delete_node(head, key):
    current = head
    previous = None
    while current and current["data"] != key:
        previous = current
        current = current["next"]
    if current is None:
        return head
    if previous is None:
        head = current["next"]
    else:
        previous["next"] = current["next"]
    return head
  • delete_node函数:这个函数用于删除链表中第一个值为key的节点。遍历链表,找到值为key的节点,然后将其从链表中移除。如果节点是头节点,则更新头节点;否则,更新前一个节点的next指针。
搜索节点
def search_node(head, key):
    current = head
    while current and current["data"] != key:
        current = current["next"]
    return current is not None
  • search_node函数:这个函数用于检查链表中是否存在值为key的节点。遍历链表,找到值为key的节点,如果找到则返回True,否则返回False。
显示链表
def display_list(head):
    current = head
    while current:
        print(current["data"], end=" -> ")
        current = current["next"]
    print("None")
  • display_list函数:这个函数用于显示链表中的所有节点。遍历链表,打印每个节点的数据,最后打印"None"表示链表结束。

通过这些方法和函数,我们可以实现链表的基本操作,包括添加、删除、搜索和显示节点。

总结

链表是一种重要的数据结构,适用于需要频繁插入和删除操作的场景。通过类的方法实现链表可以使代码更加模块化和面向对象,而不用类的方法实现链表则更加简单和直接。选择哪种方法取决于具体的应用场景和个人偏好。

07-19 20:27