您现在的位置是：首页 >学无止境 >数据结构——链表网站首页学无止境

一、介绍

        链表包含若干节点，每个节点由存储单元和指针组成。即node 包括 val （存储的内容）和next（指针，指向下一节点）

        链表有单向链表和双向链表，还有循环链表。主要区别是指针。双向链表有前指针和后指针，循环链表在此基础上最后一个节点的指针指向第一个节点。

二、实现

        定义节点类

class ListNode:
    def __init__(self,val=0,next=None):#默认值为0，指针为空
        self.val=val
        self.next=next

        在节点类的基础上实现链表。链表主要有增删查改四个操作。首先定义LinkedList类，初始化头节点。

class LinkedList:
    def __init__(self):
        self.head = None
    
    # 创建链表：通过列表初始化
    def create(self, data_list):
        self.head = None
        for data in reversed(data_list):  # 反向插入保证顺序正确
            self.prepend(data)
    
    # 头部插入，插入的新节点成为新的头节点，改变指针的指向和头节点节即可
    def prepend(self, val):
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node
    
    # 尾部插入，如果没有头节点则创建头节点，有则在最后一个节点后加入新节点
    def append(self, val):
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    # 指定位置插入，分情况，在头插入，在尾插入和在中间插入，以及索引不在链表的范围内
    def insert(self, index, val):
        if index == 0:
            self.prepend(val)
            return
        
        new_node = ListNode(val)
        current = self.head
        for _ in range(index-1):
            if not current:
                raise IndexError("Index out of range")
            current = current.next
        
        if not current:
            raise IndexError("Index out of range")
        
        new_node.next = current.next
        current.next = new_node
    
    # 删除节点（按值），删除节点即将原本指向该节点的指针指向另一节点
    def delete_by_value(self, val):
        if not self.head:
            return
        
        if self.head.val == val:
            self.head = self.head.next
            return
        
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                return
            current = current.next
    
    # 删除节点（按索引）
    def delete_by_index(self, index):
        if not self.head:
            raise IndexError("List is empty")
        
        if index == 0:
            self.head = self.head.next
            return
        
        current = self.head
        for _ in range(index-1):
            if not current.next:
                raise IndexError("Index out of range")
            current = current.next
        
        if not current.next:
            raise IndexError("Index out of range")
        
        current.next = current.next.next
    
    # 查找节点（按值是否存在）
    def search(self, val):
        current = self.head
        while current:
            if current.val == val:
                return True
            current = current.next
        return False
    
    # 查找节点（按索引获取值）
    def get(self, index):
        current = self.head
        for _ in range(index):
            if not current:
                raise IndexError("Index out of range")
            current = current.next
        if not current:
            raise IndexError("Index out of range")
        return current.val
    
    # 修改节点值
    def update(self, index, new_val):
        current = self.head
        for _ in range(index):
            if not current:
                raise IndexError("Index out of range")
            current = current.next
        if not current:
            raise IndexError("Index out of range")
        current.val = new_val
    
    # 转换为列表（便于查看）
    def to_list(self):
        result = []
        current = self.head
        while current:
            result.append(current.val)
            current = current.next
        return result

# 测试示例
if __name__ == "__main__":
    # 创建链表
    ll = LinkedList()
    ll.create([1, 2, 3])
    print("Initial list:", ll.to_list())  # [1, 2, 3]

    # 头部插入
    ll.prepend(0)
    print("After prepend 0:", ll.to_list())  # [0, 1, 2, 3]

    # 尾部插入
    ll.append(4)
    print("After append 4:", ll.to_list())  # [0, 1, 2, 3, 4]

    # 指定位置插入
    ll.insert(2, 9)
    print("After insert 9 at index 2:", ll.to_list())  # [0, 1, 9, 2, 3, 4]

    # 按值删除
    ll.delete_by_value(9)
    print("After delete value 9:", ll.to_list())  # [0, 1, 2, 3, 4]

    # 按索引删除
    ll.delete_by_index(0)
    print("After delete index 0:", ll.to_list())  # [1, 2, 3, 4]

    # 查找
    print("Search value 3:", ll.search(3))  # True
    print("Search value 9:", ll.search(9))  # False

    # 获取值
    print("Get value at index 2:", ll.get(2))  # 3

    # 修改值
    ll.update(2, 99)
    print("After update index 2 to 99:", ll.to_list())  # [1, 2, 99, 4]

一些简单的题目有leetcode 707、203、82

三、链表排序：

        适合链表的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排 序、基数排序。

        不适合链表的排序算法：希尔排序。主要是由于链表排序智能按顺序访问值。

        可以用于链表排序但不建议使用的排序算法：堆排序。