不为成仙,只为在这红尘中等你回来。

您现在的位置是:网站首页>>算法与数据结构

链表

2020年11月11日 20:06 | 分类:算法与数据结构 | 标签: Python Linked List

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

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

链表

创建链表

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


def create_linklist_head(li):
    """头插法"""
    head = Node(li[0])
    for ele in li[1:]:
        node = Node(ele)
        node.next = head
        head = node
    return head


def create_linklist_tail(li):
    """尾插法"""
    head = Node(li[0])
    tail = head
    for ele in li[1:]:
        node = Node(ele)
        tail.next = node
        tail = node
    return head


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


lk = create_linklist_head([1, 2, 3, 5])
print_linklist(lk)  # 5,3,2,1,
lk = create_linklist_tail([1, 2, 3, 5, 8])
print_linklist(lk)  # 1,2,3,5,8,

链表节点的插入

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

链表节点的删除

  • p = curNode.next
  • curNode.next = curNode.next.next 或者 curNode.next = p.next
  • del p

双链表

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

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

双链表节点的插入

  • p.next = curNode.next
  • curNode.next.prior = p
  • p.prior = curNode
  • curNode.next = p

双链表节点的删除

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