# 数组：直接通过下标访问
arr = [10, 20, 30, 40, 50]  # 创建包含5个数的数组
third = arr[2]              # 直接拿到30，一次操作

# 链表：需要从头遍历
class Node:
    def __init__(self, value):
        self.value = value   # 存的数据
        self.next = None     # 指向下一个节点的指针

head = Node(10)
head.next = Node(20)
head.next.next = Node(30)    # 构建一个3个节点的链表

# 要拿到第三个节点（30）
current = head               # 从第一个开始
count = 0
while count < 2:             # 需要走两步
    current = current.next
    count += 1
third_value = current.value  # 经过两次next才拿到30

# ---------- 数组：中间插入 ----------
arr = [1, 2, 3, 4, 5]      # 初始数组
pos = 2                    # 想在索引2（第3个位置）插入99
arr.insert(pos, 99)        # 底层会移动索引2及之后的元素
print("数组插入后:", arr)  # 输出 [1, 2, 99, 3, 4, 5]

# ---------- 链表：中间插入 ----------
class Node:
    def __init__(self, data):
        self.data = data   # 节点数据
        self.next = None   # 下一节点指针

# 手动构建链表 1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)

# 想在节点2之后插入99（已知节点2的位置）
prev = head.next          # 节点2（值为2）
new_node = Node(99)       # 新节点存99
new_node.next = prev.next # 新节点指向原来节点2的下一个（节点3）
prev.next = new_node      # 节点2指向新节点
# 现在链表为 1 -> 2 -> 99 -> 3 -> 4 -> 5

# book_system_array.py
books = ["百年孤独", "活着", "三体", "围城", "红楼梦"]  # 初始书单

print("初始书架（数组）:")
print(books)

# 1. 查找第3本书（索引2）
print(f"\n第3本书是：{books[2]}")  # 直接下标，O(1)

# 2. 在索引1（第2本书）后面插入新书"小王子"
index = 1  # 表示要在第2本书之后插入
books.insert(index + 1, "小王子")  # 注意：insert是在指定索引前插入，所以用index+1
print(f"\n在'{books[index]}'后面插入'小王子'后:")
print(books)  # ['百年孤独', '活着', '小王子', '三体', '围城', '红楼梦']

# 3. 删除"围城"（值为"围城"）
target = "围城"
if target in books:
    books.remove(target)  # 内部会移动元素
    print(f"\n删除'{target}'后:")
    print(books)  # ['百年孤独', '活着', '小王子', '三体', '红楼梦']
else:
    print(f"\n未找到'{target}'")

# book_system_linkedlist.py
class Node:
    def __init__(self, title):
        self.title = title   # 书名
        self.next = None     # 下一本书指针

class BookLinkedList:
    def __init__(self):
        self.head = None     # 第一个节点的指针

    def append_all(self, titles):
        """从列表批量添加书到链表尾部"""
        for title in titles:
            self.append(title)

    def append(self, title):
        """在链表末尾添加一本书"""
        new_node = Node(title)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:          # 找到最后一个节点
            last = last.next
        last.next = new_node

    def get_by_index(self, index):
        """按索引查找书（从0开始），返回节点"""
        current = self.head
        count = 0
        while current:
            if count == index:
                return current
            current = current.next
            count += 1
        return None  # 越界返回None

    def insert_after(self, index, title):
        """在指定索引节点之后插入新书"""
        node = self.get_by_index(index)
        if node is None:
            print(f"索引{index}不存在，无法插入")
            return
        new_node = Node(title)
        new_node.next = node.next
        node.next = new_node

    def remove_by_value(self, title):
        """删除指定书名的第一本书"""
        current = self.head
        prev = None
        while current:
            if current.title == title:
                if prev is None:          # 要删除的是头节点
                    self.head = current.next
                else:
                    prev.next = current.next
                print(f"已删除'{title}'")
                return
            prev = current
            current = current.next
        print(f"未找到'{title}'")

    def display(self):
        """打印整个书架顺序"""
        titles = []
        current = self.head
        while current:
            titles.append(current.title)
            current = current.next
        print("书架（链表形式）:", " -> ".join(titles))

# ---------- 测试 ----------
books_list = BookLinkedList()
books_list.append_all(["百年孤独", "活着", "三体", "围城", "红楼梦"])

print("初始书架（链表）:")
books_list.display()

# 1. 查找第3本书（索引2）
node = books_list.get_by_index(2)
print(f"\n第3本书是：{node.title if node else '不存在'}")

# 2. 在索引1（第2本书）后面插入新书"小王子"
books_list.insert_after(1, "小王子")
print(f"\n在'活着'后面插入'小王子'后:")
books_list.display()

# 3. 删除"围城"
books_list.remove_by_value("围城")
print(f"\n删除'围城'后:")
books_list.display()