1.1 概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

1.2 存储原则 

（1）用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

（2）链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

​注：链式存储是数据结构中最常用的存储方式之一，它不仅可表示线性表，而且可表示各种非线性的数据结构。

1.3 单链表结构

data

next

data域--存放结点值的数据域

next域--存放结点的直接后继的地址（位置）的指针域(链域)

头指针——单链表中每个结点的存储地址是存放在它的前趋结点next域中，而开始结点没有前趋，所以应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。

终端节点——终端节点没有后继，故终端结点的指针域为空，即NULL。

1.4 单链表插入、删除操作

（1）插入节点操作

①  插入指针s指向的节点X

 ② 令s-->next = p-->next 

p-->next = s  插入后

 

(2) 删除节点操作

 

①删除节点b

令p-->next = p-->next-->next

 1.5 代码实现

class Node:
    """链表节点类"""
    def __init__(self, data):
        self.data = data  # 节点数据
        self.next = None  # 指向下一个节点的指针

class LinkedList:
    """单链表类"""
    def __init__(self):
        """初始化空链表"""
        self.head = None  # 链表头节点
        self.size = 0    # 链表长度

    def __len__(self):
        """返回链表长度"""
        return self.size

    def is_empty(self):
        """检查链表是否为空"""
        return self.size == 0

    def insert_at_beginning(self, data):
        """在链表头部插入新节点"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def insert_at_end(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
        self.size += 1

    def insert_at_position(self, position, data):
        """在指定位置插入新节点"""
        if position < 0 or position > self.size:
            raise IndexError("位置超出链表范围")
        
        if position == 0:
            self.insert_at_beginning(data)
        elif position == self.size:
            self.insert_at_end(data)
        else:
            new_node = Node(data)
            current = self.head
            for _ in range(position - 1):
                current = current.next
            new_node.next = current.next
            current.next = new_node
            self.size += 1

    def delete_at_beginning(self):
        """删除链表头部节点"""
        if self.is_empty():
            raise Exception("链表为空")
        self.head = self.head.next
        self.size -= 1

    def delete_at_end(self):
        """删除链表尾部节点"""
        if self.is_empty():
            raise Exception("链表为空")
        
        if self.size == 1:
            self.head = None
        else:
            current = self.head
            while current.next.next:
                current = current.next
            current.next = None
        self.size -= 1

    def delete_at_position(self, position):
        """删除指定位置的节点"""
        if position < 0 or position >= self.size:
            raise IndexError("位置超出链表范围")
        
        if position == 0:
            self.delete_at_beginning()
        elif position == self.size - 1:
            self.delete_at_end()
        else:
            current = self.head
            for _ in range(position - 1):
                current = current.next
            current.next = current.next.next
            self.size -= 1

    def delete_by_value(self, value):
        """删除包含特定值的第一个节点"""
        if self.is_empty():
            return False
        
        if self.head.data == value:
            self.delete_at_beginning()
            return True
            
        current = self.head
        while current.next:
            if current.next.data == value:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False

    def search(self, value):
        """查找链表中是否存在特定值"""
        current = self.head
        position = 0
        while current:
            if current.data == value:
                return position
            current = current.next
            position += 1
        return -1

    def get_at_position(self, position):
        """获取指定位置的节点值"""
        if position < 0 or position >= self.size:
            raise IndexError("位置超出链表范围")
        
        current = self.head
        for _ in range(position):
            current = current.next
        return current.data

    def update_at_position(self, position, new_value):
        """更新指定位置的节点值"""
        if position < 0 or position >= self.size:
            raise IndexError("位置超出链表范围")
        
        current = self.head
        for _ in range(position):
            current = current.next
        current.data = new_value

    def reverse(self):
        """反转链表"""
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

    def display(self):
        """打印链表内容"""
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements))

    def clear(self):
        """清空链表"""
        self.head = None
        self.size = 0


# 测试单链表
if __name__ == "__main__":
    print("创建链表并插入元素")
    ll = LinkedList()
    
    # 在头部插入
    ll.insert_at_beginning(10)
    ll.insert_at_beginning(20)
    print("头部插入后:", end=" ")
    ll.display()  # 20 -> 10
    
    # 在尾部插入
    ll.insert_at_end(30)
    ll.insert_at_end(40)
    print("尾部插入后:", end=" ")
    ll.display()  # 20 -> 10 -> 30 -> 40
    
    # 在指定位置插入
    ll.insert_at_position(2, 50)
    print("位置2插入50:", end=" ")
    ll.display()  # 20 -> 10 -> 50 -> 30 -> 40
    
    # 删除操作
    ll.delete_at_beginning()
    print("删除头部后:", end=" ")
    ll.display()  # 10 -> 50 -> 30 -> 40
    
    ll.delete_at_end()
    print("删除尾部后:", end=" ")
    ll.display()  # 10 -> 50 -> 30
    
    ll.delete_at_position(1)
    print("删除位置1后:", end=" ")
    ll.display()  # 10 -> 30
    
    # 删除特定值
    ll.insert_at_end(60)
    ll.insert_at_end(70)
    print("插入60和70后:", end=" ")
    ll.display()  # 10 -> 30 -> 60 -> 70
    
    ll.delete_by_value(60)
    print("删除值60后:", end=" ")
    ll.display()  # 10 -> 30 -> 70
    
    # 查找操作
    print("值30的位置:", ll.search(30))  # 1
    print("值100的位置:", ll.search(100))  # -1
    
    # 获取和更新
    print("位置1的值:", ll.get_at_position(1))  # 30
    ll.update_at_position(1, 35)
    print("更新位置1为35后:", end=" ")
    ll.display()  # 10 -> 35 -> 70
    
    # 反转链表
    ll.reverse()
    print("反转链表后:", end=" ")
    ll.display()  # 70 -> 35 -> 10
    
    # 清空链表
    ll.clear()
    print("清空链表后:", end=" ")
    ll.display()  # (空)
    print("链表长度:", len(ll))  # 0

代码运行效果：

操作时间复杂度分析： 

头部插入	O(1)	直接修改头指针
尾部插入	O(n)	需要遍历到链表尾部
指定位置插入	O(n)	最坏情况需要遍历到指定位置
头部删除	O(1)	直接修改头指针
尾部删除	O(n)	需要遍历到倒数第二个节点
指定位置删除	O(n)	最坏情况需要遍历到指定位置
搜索	O(n)	需要遍历链表
反转	O(n)	需要遍历整个链表