1.单链表的逻辑结构与存储结构
1.1逻辑结构
逻辑结构：数据元素之间的逻辑关系
集合、线性结构（一对一）、树形结构（一对多）、图结构（多对多）
1.2存储结构
存储结构：顺序存储、链式存储、索引存储、散列存储
顺序存储（顺序表）：逻辑上相邻的元素物理位置也相邻
链式存储（单链表）：逻辑上相邻的元素物理位置不一定相邻
2.单链表的定义
定义单链表：
class ListNode: def __init__(self,val=0,next=None): self.val=val self.next=next
带头结点的单链表（写代码方便）：
不带头结点的单链表（写代码麻烦）：
3.插入元素
3.1带头节点的单链表
#在第i个位置插入元素 def Insert(head,i,elem): assert i >=0 cur = head while i!=0: i-=1 cur=cur.next if not cur: return False temp=cur.next cur.next=elem elem.next=temp return True
3.2不带头节点的单链表
#在第i个位置插入元素 def Insert(i,elem) global head assert i>=0 if i==0: elem.next=head head=elem cue=head while i>1: i-=1 cur=cur.next if not cur: return Flase temp=cur.next cur.next=elem elem.next=temp return True
4.删除元素
def ListDelete( head, i) : assert i >= 0 cur = head while i != 0: i -= 1 cur = cur.next if not cur.next: return False cur.next = cur.next.next return True
5.创建单链表
5.1尾插法创建单链表
带头节点的单链表：
def BuildLink_Tai1(1): head = ListNode( ) temp = head for elem in l: temp.next = ListNode(elem) temp = temp.next return head head = BuildLink_Tail([1，2，3，4]) while head.next: head = head.next print( head.val)
不带头节点的单链表：
def BuildLink_Tail(1): if not l: return None head = ListNode(l[0]) temp = head for elem in 1[1:]: temp.next = ListNode(elem) temp = temp.next return head head = BuildLink_Tail([1，2，3，4]) while head: print( head.val) head = head.next
5.2头插法创建单链表
带头节点的单链表：
def BuildLink_Head( 1) : head = ListNode() for elem in l: temp = head.next head.next = ListNode(elem,temp) return head
不带头节点的单链表：
def BuildLink_Head(1): head = None for elem in l: head = ListNode(elem，head) return head
6.双链表
解决单链表无法逆向索引的问题
class DLinkNode: def __init__(self, val=0,next=None,prior): self.val = val self.next = next self.prior = prior
7.循环链表
7.1循环单链表
从一个节点出发可以找到其他任何节点
7.2循环双链表
从头找到尾和从尾找到头时间复杂度都是O(1)
