链表的相关概念
在顺序表中，由于逻辑上相邻的元素其物理位置也相邻，因此可以随机存取顺序表中的任何一个元素。但是，顺序表也存在着如下缺点：
- 插入和删除运算需要移动大量的元素
- 顺序表中的存储空间必须事先分配好，而事先分配的存储单元大小可能不适合问题的需要。对很多高级程序设计语言来说，事先分配好存储空间后不容易调整
采用链式存储的线性表称为链表，链表可以分为单向链表、双向链表、循环链表。
所谓线性表的链式存储，是指采用一组任意的存储单元存放线性表中的元素。这组存储单元可以是连续的，也可以是不连续的。为了表示这些元素之间的逻辑关系，除了需要存储元素本身的信息外，还需要存储指示其后继元素的地址信息。这两部分组成的存储结构，称为结点。结点包括两个域：数据域和指针域。其中，数据域存放数据元素的信息，指针域存放元素的直接后继的存储地址
用python实现单向链表
class ListNode:"""节点类"""def __init__(self, x):#当前节点的值(数据域)self.val = x#当前节点的后继节点的地址(指针域)self.next = Noneclass LinkedList:"""单向链表类"""def __init__(self):self.head = Noneself.len = 0def size(self):"""返回链表的长度"""return self.lendef insert(self, pos, val):"""在指定的位置插入传入的值"""if pos < 0 or pos > self.size():raise ValueError("Invalid position")newNode = ListNode(val)if pos == 0:newNode.next = self.headself.head = newNodeelse:prev = self.headfor _ in range(pos-1):prev = prev.nextnewNode.next = prev.nextprev.next = newNodeself.len += 1def delete(self, pos):"""删除指定位置的值"""if pos < 0 or pos >= self.size():raise ValueError("Invalid position")if pos == 0:self.head = self.head.nextelse:prev = self.headfor _ in range(pos-1):prev = prev.nextprev.next = prev.next.nextself.len -= 1def update(self, pos, val):"""更新指定位置的值"""if pos < 0 or pos >= self.size():raise ValueError("Invalid position")current = self.headfor _ in range(pos):current = current.nextcurrent.val = valdef search(self, val):"""根据传入的值查找对应的节点对象查到：返回节点对象未查到：返回None"""current = self.headwhile current:if current.val == val:return currentcurrent = current.nextreturn Nonedef index(self, val):"""根据传入的值查找对应的索引查到：返回索引未查到：返回-1"""i = 0current = self.headwhile current:if current.val == val:return ii += 1current = current.nextreturn -1def LinkedPrint(self):"""打印"""current = self.headwhile current:print(current.val, end="->")current = current.nextprint(None)def test():"""测试"""L = LinkedList()L.insert(0, 5)L.insert(0, 6)L.insert(0, 8)L.insert(0, 4)L.insert(0, 'a')L.insert(0, 'd')L.insert(0, 't')L.insert(0, 2)L.insert(0, 3)L.insert(0, 7)L.insert(2, 20)L.insert(4, 'tt')L.delete(4)L.delete(0)L.update(0, 30)print(L.search('t'))print(L.index('t'))L.LinkedPrint()print(L.size())test()
