1.单链表的逻辑结构与存储结构

1.1逻辑结构

逻辑结构：数据元素之间的逻辑关系

集合、线性结构（一对一）、树形结构（一对多）、图结构（多对多）

1.2存储结构

存储结构：顺序存储、链式存储、索引存储、散列存储

顺序存储（顺序表）：逻辑上相邻的元素物理位置也相邻

链式存储（单链表）：逻辑上相邻的元素物理位置不一定相邻

2.单链表的定义

定义单链表：

class ListNode:def __init__(self,val=0,next=None):self.val=valself.next=next

带头结点的单链表（写代码方便）：

不带头结点的单链表（写代码麻烦）：

3.插入元素

3.1带头节点的单链表

#在第i个位置插入元素
def Insert(head,i,elem):assert i >=0cur = headwhile i!=0:i-=1cur=cur.nextif not cur:return Falsetemp=cur.nextcur.next=elemelem.next=tempreturn True

3.2不带头节点的单链表

#在第i个位置插入元素
def Insert(i,elem)global headassert i>=0if i==0:elem.next=headhead=elemcue=headwhile i>1:i-=1cur=cur.nextif not cur:return Flasetemp=cur.nextcur.next=elemelem.next=tempreturn True

4.删除元素

def ListDelete( head, i) :assert i >= 0cur = headwhile i != 0:i -= 1cur = cur.nextif not cur.next:return Falsecur.next = cur.next.nextreturn True

5.创建单链表

5.1尾插法创建单链表

带头节点的单链表：

def BuildLink_Tai1(1):head = ListNode( )temp = headfor elem in l:temp.next = ListNode(elem)temp = temp.nextreturn headhead = BuildLink_Tail([1，2，3，4])
while head.next:head = head.nextprint( head.val)

不带头节点的单链表：

def BuildLink_Tail(1):if not l:return Nonehead = ListNode(l[0])temp = headfor elem in 1[1:]:temp.next = ListNode(elem)temp = temp.nextreturn headhead = 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.nexthead.next = ListNode(elem,temp)return head

不带头节点的单链表：

def BuildLink_Head(1):head = Nonefor elem in l:head = ListNode(elem，head)return head

6.双链表

解决单链表无法逆向索引的问题

class DLinkNode:def __init__(self, val=0,next=None,prior):self.val = valself.next = nextself.prior = prior

7.循环链表

7.1循环单链表

从一个节点出发可以找到其他任何节点

7.2循环双链表

从头找到尾和从尾找到头时间复杂度都是O(1)