1. 基本概念
链表是一种基本的数据结构，用于存储一组有序的数据元素。链表由节点组成，每个节点包含两个域：数据域和指针域。数据域用来存储数据元素，指针域用来指向链表中的下一个节点。
链表可以分为单向链表、双向链表和循环链表。单向链表只能够从头节点开始向后遍历，双向链表可以从头节点和尾节点开始向前或向后遍历，而循环链表则是在单向或双向链表的基础上将尾节点指向头节点，形成一个环。
链表的优点是可以动态地进行插入和删除操作，而且不需要像数组一样事先确定存储空间的大小。缺点是查询操作时间复杂度较高，需要从头节点开始遍历，而且需要消耗额外的空间来存储指针域。
重点归纳：
- 顺序表与链表最坏时间复杂度对比:
在大O表示法中，时间复杂度的增长趋势通常可以分为以下几类：
- 常数阶O(1)：执行时间与问题规模无关，常量时间复杂度，如对一个元素进行常量操作。
- 线性阶O( n n n)：执行时间与问题规模成正比，如遍历一个数组。
- 平方阶O( n 2 n^2 n2)：执行时间随问题规模的增加呈平方增加，如冒泡排序。
- 指数阶O( 2 n 2^n 2n)：执行时间随问题规模的增加呈指数增加，如求解汉诺塔问题。
Python中实现a, b 值交换：a,b = b,a (Tuple 类型)，Python中改变的是a,b的对象内存的地址，而不是改变对象内存内的元素
class Node: def __init__(self, elem): self.elem = elem self.next = None self.prev = None class SingleLinkList: #构建单向列表 def __init__(self, node = None): self._head = node #_head 是第一个节点，包含第一个元素和下一个节点的地址 def is_empty(self): return self._head == None def append(self, item): node = Node(item) #创建添加的节点 if self._head == None: #判断链表是否为空(用self对象（或者说实例）调用方法is_empty) self._head = node #如果头节点为空，把新添加的节点作为头节点 else: cur = self._head #如果头节点不为空，指定头节点为当前节点（**cur为Node类实例**）, cur 与self._head 地址一样 # print(cur) #测试一下是否能链接 # print(self._head) # print(self._head.next) while cur.next != None: #在节点中的next不为空的情况下(不是最后一个节点) cur = cur.next #遍历列表，把下一节点地址赋给此几点 # print(cur) cur.next = node #类的实例化，cur.next也是Node类！cur.next存入node的地址，同时self._head.next 也被赋值！！！ def length(self): cur = self._head #遍历开始 count = 0 while cur != None: count += 1 cur = cur.next #遍历 return count def travel(self): cur = self._head # 遍历开始 while cur != None: print(cur.elem,end=",") cur = cur.next # 遍历 def headadd(self, item): node = Node(item) if self.is_empty(): self._head = node else: node.next = self._head self._head = node def addatpos(self, pos, item): node = Node(item) count = 1 cur = self._head while count != pos: count += 1 cur = cur.next node.next = cur.next cur.next = node def search(self, item): cur = self._head while cur != None: if cur.elem == item: return "bingo" break cur = cur.next return "Nogo" class DoubleLinkList(SingleLinkList): #构建双向列表 def append(self, item): node = Node(item) if self._head == None: self._head = node else: cur = self._head while cur.next != None: cur = cur.next #遍历列表 cur.next = node #链接下一节点 node.prev = cur # print(cur.prev) #验证一下地址是不是能衔接上 # print(cur)#验证一下地址是不是能衔接上 # print(cur.next,end="\n\n")#验证一下地址是不是能衔接上 def addatpos(self, pos, item): node = Node(item) count = 1 cur = self._head while count != pos: count += 1 cur = cur.next node.next = cur.next node.prev = cur cur.next = node cur.next.prev = node #-------------------------以下为测试运行--------------------- # sll = SingleLinkList() # sll.append(1) # sll.append(2) # sll.append(1) # sll.append(4) # sll.headadd(10000) # sll.addatpos(1,999999) # sll.travel() # print(sll.search(2)) dll = DoubleLinkList() dll.append(1) dll.append(2) dll.append(3) dll.append(4) dll.append(5) dll.append(1322) dll.addatpos(2, 88888) print(dll.travel())
