数据结构：链表

2023-08-17 40

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构：链表

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

1.1逻辑结构

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

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

1.2存储结构

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

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

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

2.单链表的定义

定义单链表：

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

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

0748abb7af77cc20a11522d5d871d985_649c603d2c3f9e22c7139f91c183fa2b.png

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

62389ba01e756d357a79e50934d0120b_afdffa9740eaa825743770b29b2c5a89.png

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.双链表

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

cc394a92546d0727e0fa0aa86ffd2d7b_b529d91fd83020ea81741567c0c0c584.png

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

7.循环链表

7.1循环单链表

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

1fbc0090dc91f947aaaffd99220285ed_0ebfa60b8f94a82badd8037ae8391704.png

7.2循环双链表

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

5bc253072a4be86fe998345048de1d4f_8ced43b7eb4bd35fc69dca61f94b2952.png