基于Python3的数据结构与算法 - 16 链表

目录

链表

1. 创建链表 

2. 链表的插入和删除

3. 双链表 

4. 链表总结

链表

链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点得指针next。通过节点之间的相互连接，最终串联成一个链表。

class Node:
    def __init__(self,item):
        self.item = item
        self.next = None
        
        
a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c

print(a.next.item)
print(a.next.next.item)

1. 创建链表 

创建链表共有两种方法：头插法和尾插法。

链表总有一个头节点和一个尾节点。

使用头插法创建链表（将一个列表变为链表）

class Node:
    def __init__(self, item):
        self.item = item
        self.next = None


def create_linklist_head(li):
    head = Node(li[0])  # 定义头节点
    for element in li[1:]:
        node = Node(element)
        node.next = head  # 将插入进来的元素与head连接起来
        head = node  # # 再将node定义为头节点
    return head


def print_linklist(lk):
    while lk:
        print(lk.item, end=',')
        lk = lk.next


lk = create_linklist([1, 2, 3])
# print(lk.item)   # 返回头节点
print_linklist_head(lk)

使用尾插法创建列表 ：

def create_linklist_tail(li):
    head = Node(li[0])  # 定义头节点
    tail = head # 此时只有一个元素
    for element in li[1:]:
        node = Node(element)
        tail.next = node  # 新来的元素连接到tail后面
        tail = node     # 再将node定义为尾节点
    return head

lk = create_linklist_tail([1,2,3,4,5,6])
print_linklist(lk)

2. 链表的插入和删除

 列表的插入时间复杂度为O(n), 但是链表不是，因为链表不是顺序存储。

链表的插入分为两步：

• 先将4与2相连接
• 再将1与4相连接

p.next = curNode.next
curNode.next = p

如果此时想再将元素4删除：

• 先将1和2链接起来
• 再将4删除

p = curNode.next
curNode.next = curNode.next.next
del p

3. 双链表 

 双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点。

class Node(object):
    def __init__(self. item = None):
        self.item = item
        self.next = None
        self.prior = None

双链表的插入：

• 先将2与3相互连接
• 再将1与2相互连接

p.next = curNode.next
curNode.next.prioi = p
p.prior = curNode
curNode.next = p

双链表的删除：

• 将1与3互相连接
• 再将2删除 

p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p

4. 链表总结

顺序表（列表/数组）与链表复杂度分析：

• 按元素查找：都是挨个遍历，复杂度都为O(n).
• 按下标查找：列表中直接存放地址，复杂度为O(1), 链表复杂度为O(n).
• 在某元素后插入：列表为O(n)，链表为O(1)
• 删除某元素：列表为O(n),链表为O(1)

链表在插入和删除的操作上明显快与顺序表。

链表的内存分配更加灵活。