编程基础 —— 链表

目录

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

2 单链表的定义

3 插入元素

4 删除元素

5 创建单链表

（1）尾插法

（2）头插法

6 双链表

7 循环链表

（1）循环单链表

（2）循环双链表

8 练习

（1）移除链表元素

（2）旋转链表

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

• 逻辑结构：数据元素之间的逻辑关系
  • 集合、线性结构（一对一）、树形结构（一对多）、图结构（多对多）
• 存储结构：顺序存储、链式存储、索引存储、散列存储
  • 顺序存储（顺序表）：逻辑上相邻的元素物理位置也相邻
  • 链式存储（单链表）：逻辑上相邻的元素物理位置不一定相邻

2 单链表的定义

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

• 带头节点的单链表（写代码方便）
• 不带头节点的单链表（写代码麻烦）

3 插入元素

# 在第i个位置插入elem
def Inster(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

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 创建单链表

（1）尾插法

def BulidLink_Head(l):
    head = ListNode()
    temp = head    
    for elem in l:
        temp.next = ListNode(elem)
        temp = temp.next
    return head
 
head = BulidLink_Tail([1,2,3,4])
while head.next:
    head = head.next
    print(head.val)

（2）头插法

def BulidLink_Head(l):
    head = ListNode()
    temp = head    
    for elem in l:
        temp = head.next
        head.next = ListNode(elem, temp)
    return head

6 双链表

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

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

7 循环链表

（1）循环单链表

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

（2）循环双链表

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

8 练习

（1）移除链表元素

一个链表的头节点head和一个整数val，请删除链表中所有满足Node.val == val的节点，并返回新的头节点。

class solution:
    def removeElements(self, head, val):
        head = ListNode(next = head)
        pre = head
        while pre.next:
            if pre.next.val == val:
                pre.next = pre.next.next
            else:
                pre = pre.next
        return head.next

（2）旋转链表

一个链表的头节点head ,旋转链表;将链表每个节点向右移动k个位置。

class solution:
    def rotateRight(self, head, k):
        if not head:
            return None
        length = 0
        temp = head
        while temp.next:
            length += 1
            temp = temp.next
        temp.next = head
        k = k % (length + 1)
        temp = head
        for i in range(length - k):
            temp = temp.next
        head = temp.next
        temp.next = None
        return head