1 概述

链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域和指针域，python虽然弱化了指针的概念，但是思想一直在。链表是通过指针链接各个节点的数据结构

在这里插入图片描述

一个简单的链表class

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.next.item)
print(a.next.next.next)

"""
OUT 
3
None
"""

2 创建链表

2.1 头插法

头插法是把结点插到头结点后面，先把新加入的结点的next指向原来head指向的结点，再把head改成新结点

2.2 尾插法

尾插法是把结点插到尾结点前面，想让新节点的next指向tail，然后再让tail更新成新节点

2.3 代码

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

class HandleNode:
    def create_linklist_head(self,li):
        head = Node(li[0])
        for element in li[1:]:
            node = Node(element)
            node.next = head
            head = node
        return head

    def create_linklist_tail(self,li):
        head = Node(li[0])
        tail = head
        for element in li[1:]:
            node = Node(element)
            tail.next = node
            tail = node
        return head

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

3 双端链表

一个结点有两个指针，分别指向前个结点和后一个结点

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


class HandleDouNode:
    def create_node_head(self,li):
        head = DoubleNode(li[0])
        for element in li[1:]:
            node = DoubleNode(element)
            node.next = head # 新节点的指针链接到原来head结点
            head.prior = node # 原来head结点的上一个指针链接到node
            head = node # 头节点指向node
        return head

    def create_node_tail(self,li):
        head = DoubleNode(li[0]) 
        tail = head
        for element in li[1:]:
            node = DoubleNode(element)
            tail.next = node #原来的尾部结点的下一个指针链接到node
            node.prior = tail # node结点的前一个指针连接到原来尾部
            tail = node  # 修改尾部指针为node
        return head

    def print_node(self,head):
        while head:
            print(head.item,end=',')
            head = head.next

hdn = HandleDouNode()
head = hdn.create_node_tail([1,2,3])
print(head.item)
print(head.next.item)
print(head.next.prior.item)
"""
OUT
1
2
1
"""