Python教程

python数据结构之双向链表

本文主要是介绍python数据结构之双向链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

python数据结构之双向链表

  1. 双向链表可以是循环的也可以是不循环的；
  2. 主要有left前驱指针，right后驱指针；

代码部分

  1. 结点类的创建
class Node:
    def __init__(self, value):
        self.data = value
        self.prior = None
        self.after = None
  1. 初始化链表
def init_list(head_ptr: Node):
    data_arr = [10, 20, 30, 40, 50, 60]
    ptr = head_ptr
    for i in range(len(data_arr)):
        new_node = Node(data_arr[i])
        new_node.prior = ptr
        new_node.after = None
        ptr.after = new_node
        ptr = new_node
    ptr.after = head_ptr
    head_ptr.prior = ptr
  1. 增加单个数据结点
def add_node(head_ptr: Node, value: int):
    new_node = Node(value)
    ptr = head_ptr
    while ptr.after != head_ptr:
        ptr = ptr.after
    new_node.after = ptr.after
    new_node.prior = ptr
    ptr.after = new_node
  1. 通过索引插入数据结点
def Insert_Node_index(head_ptr, index: int, value: int):
    new_node = Node(value)
    index_loc = 0
    flag = True
    if index == 0:
        ptr = head_ptr
        new_node.after = head_ptr
        head_ptr.prior = new_node
        while ptr.after != head_ptr:
            ptr = ptr.after
        new_node.prior = ptr
        ptr.after = new_node
        head_ptr = new_node
        flag = False
    elif index > 0:
        ptr = head_ptr
        while True:
            if index_loc == (index - 1):
                new_node.after = ptr.after
                new_node.prior = ptr.prior
                ptr.after.prior = new_node
                ptr.after = new_node
                flag = False
                break
            index_loc += 1
            ptr = ptr.after
            if ptr == head_ptr:
                break
    if flag:
        new_node.after = head_ptr
        new_node.prior = head_ptr.prior
        head_ptr.prior.after = new_node
    return head_ptr
  1. 通过值的寻找插入
def Insert_Node_Value(head_ptr, find_value, new_value):
    new_node = Node(new_value)
    ptr = head_ptr
    while ptr.data != find_value:
        ptr = ptr.after
        if ptr == head_ptr:
            break
    new_node.after = ptr
    new_node.prior = ptr.prior
    ptr.prior.after = new_node
    ptr.prior = new_node
  1. 通过索引删除数据
def Del_Node_Index(head_ptr, index):
    index_loc = 0
    ptr = head_ptr
    if index == 0:
        head_ptr.prior.after = head_ptr.after
        head_ptr.after.prior = head_ptr.prior
        head_ptr = head_ptr.after
    elif index > 0:
        while True:
            if index == index_loc:
                ptr.prior.after = ptr.after
                ptr.after.prior = ptr.prior
                break
            index_loc += 1
            ptr = ptr.after
    return head_ptr
  1. 通过值寻找删除结点
def Del_Node_Value(head_ptr, find_value):
    ptr = head_ptr
    if head_ptr.data == find_value:
        head_ptr.prior.after = head_ptr.after
        head_ptr.after.prior = head_ptr.prior
        head_ptr = head_ptr.after
        return head_ptr
    else:
        while True:
            if ptr.data == find_value:
                ptr.prior.after = ptr.after
                ptr.after.prior = ptr.prior
                break
            ptr = ptr.after
            if ptr == head_ptr:
                break
    return head_ptr
  1. 查找所有节点数值
def Query_Index_Node(head_ptr, index):
    loc_index = 0
    find_data = -1
    ptr = head_ptr
    while True:
        if index == loc_index:
            find_data = ptr.data
            break
        loc_index += 1
        ptr = ptr.after
        if ptr == head_ptr:
            break
    return find_data
  1. 查找值的索引
def Query_Value_Index(head_ptr, find_data):
    index = -1
    find_index = -1
    ptr = head_ptr
    while True:
        index += 1
        if ptr.data == find_data:
            find_index = index
        ptr = ptr.after
        if ptr == head_ptr:
            break
    return find_index
  1. 输出数据
def Print_all(head_ptr):
    ptr = head_ptr
    while True:
        print(ptr.data, end="\t")
        ptr = ptr.after
        if ptr == head_ptr:
            break

结论

class Node:
    def __init__(self, value):
        self.data = value
        self.prior = None
        self.after = None


def init_list(head_ptr: Node):
    data_arr = [10, 20, 30, 40, 50, 60]
    ptr = head_ptr
    for i in range(len(data_arr)):
        new_node = Node(data_arr[i])
        new_node.prior = ptr
        new_node.after = None
        ptr.after = new_node
        ptr = new_node
    ptr.after = head_ptr
    head_ptr.prior = ptr


def add_node(head_ptr: Node, value: int):
    new_node = Node(value)
    ptr = head_ptr
    while ptr.after != head_ptr:
        ptr = ptr.after
    new_node.after = ptr.after
    new_node.prior = ptr
    ptr.after = new_node


def Insert_Node_index(head_ptr, index: int, value: int):
    new_node = Node(value)
    index_loc = 0
    flag = True
    if index == 0:
        ptr = head_ptr
        new_node.after = head_ptr
        head_ptr.prior = new_node
        while ptr.after != head_ptr:
            ptr = ptr.after
        new_node.prior = ptr
        ptr.after = new_node
        head_ptr = new_node
        flag = False
    elif index > 0:
        ptr = head_ptr
        while True:
            if index_loc == (index - 1):
                new_node.after = ptr.after
                new_node.prior = ptr.prior
                ptr.after.prior = new_node
                ptr.after = new_node
                flag = False
                break
            index_loc += 1
            ptr = ptr.after
            if ptr == head_ptr:
                break
    if flag:
        new_node.after = head_ptr
        new_node.prior = head_ptr.prior
        head_ptr.prior.after = new_node
    return head_ptr


def Insert_Node_Value(head_ptr, find_value, new_value):
    new_node = Node(new_value)
    ptr = head_ptr
    while ptr.data != find_value:
        ptr = ptr.after
        if ptr == head_ptr:
            break
    new_node.after = ptr
    new_node.prior = ptr.prior
    ptr.prior.after = new_node
    ptr.prior = new_node


def Del_Node_Index(head_ptr, index):
    index_loc = 0
    ptr = head_ptr
    if index == 0:
        head_ptr.prior.after = head_ptr.after
        head_ptr.after.prior = head_ptr.prior
        head_ptr = head_ptr.after
    elif index > 0:
        while True:
            if index == index_loc:
                ptr.prior.after = ptr.after
                ptr.after.prior = ptr.prior
                break
            index_loc += 1
            ptr = ptr.after
    return head_ptr


def Del_Node_Value(head_ptr, find_value):
    ptr = head_ptr
    if head_ptr.data == find_value:
        head_ptr.prior.after = head_ptr.after
        head_ptr.after.prior = head_ptr.prior
        head_ptr = head_ptr.after
        return head_ptr
    else:
        while True:
            if ptr.data == find_value:
                ptr.prior.after = ptr.after
                ptr.after.prior = ptr.prior
                break
            ptr = ptr.after
            if ptr == head_ptr:
                break
    return head_ptr


def Query_Index_Node(head_ptr, index):
    loc_index = 0
    find_data = -1
    ptr = head_ptr
    while True:
        if index == loc_index:
            find_data = ptr.data
            break
        loc_index += 1
        ptr = ptr.after
        if ptr == head_ptr:
            break
    return find_data


def Query_Value_Index(head_ptr, find_data):
    index = -1
    find_index = -1
    ptr = head_ptr
    while True:
        index += 1
        if ptr.data == find_data:
            find_index = index
        ptr = ptr.after
        if ptr == head_ptr:
            break
    return find_index


def Print_all(head_ptr):
    ptr = head_ptr
    while True:
        print(ptr.data, end="\t")
        ptr = ptr.after
        if ptr == head_ptr:
            break


if __name__ == '__main__':
    head = Node(1)
    init_list(head)
    head = Insert_Node_index(head, 2, 80)
    Insert_Node_Value(head, 55, 9892)
    Print_all(head)

    head = Del_Node_Index(head, 0)
    head = Del_Node_Value(head, 10)
    print()
    Print_all(head)
    print()
    print(Query_Index_Node(head, 0))
    print(Query_Value_Index(head, 00))
    head_one = Node(8273)
    init_list(head_one)
这篇关于python数据结构之双向链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航