线性结构_双向链表_删除节点数据-【官方】百战程序员_IT在线教育培训机构


xxxxxxxxxx
def __init__(self): #初始化双链表
def get(self, index: int) -> int: #获取双链表中第index个节点的值
def addAtHead(self, val: int) -> None: #在双链表的第一个元素之前添加一个值为val的节点。
def addAtTail(self, val: int) -> None: #将值为val的节点追加到链表的最后一个元素。
def addAtIndex(self, index: int, val: int) -> None: #在链表中的第index个节点之前添加值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点，如果index小于0，则在头部插入节点。
def deleteAtIndex(self, index: int) -> None: #如果索引index有效，则删除链表中的第index个节点。 
def getNode(self, index: int) -> node: #获取节点
def addNode(self, first: node, second: node, val: int) -> None: #添加节点

初始化双链表


xxxxxxxxxx
class node:
    def __init__(self, val):
        self.val = val
        self.pre = None #指向前面节点的指针
        self.next = None #指向后面节点的指针


xxxxxxxxxx
class MyLinkedList:

    def __init__(self):
        self.head = node(-1)  #虚拟头节点
        self.tail = node(-1)  #虚拟尾节点
        self.head.next = self.tail # 让虚拟头节点指向虚拟尾节点
        self.tail.pre = self.head #虚拟尾节点指回虚拟头节点
        self.size = 0

获取数据

获取双链表中第index个节点


xxxxxxxxxx
def get(self, index: int) -> int:
    if index < 0 or index >= self.size:
        return -1

    curr = self.getNode(index)
        return curr.val

我们来下如何来写这个getNode方法，我们需要在方法中反复使用


xxxxxxxxxx
    def getNode(self, index: int) -> node:
        if index < self.size // 2:
            curr = self.head
            for i in range(index + 1):
                curr = curr.next
        else:
            curr = self.tail
            for i in range(self.size - index):
                curr = curr.pre
        return curr

增加数据

编写addNode函数


xxxxxxxxxx
def addNode(self, first: node, second: node, val: int) -> None:
    temp_node = node(val)
    temp_node.next = second
    second.pre = temp_node
    first.next = temp_node
    temp_node.pre = first
    self.size += 1

在单链表的第一个元素之前添加一个值为val的节点


xxxxxxxxxx
def addAtHead(self, val: int) -> None:
    self.addNode(self.head, self.head.next, val)

将值为val的节点追加到链表的最后一个元素


xxxxxxxxxx
def addAtTail(self, val: int) -> None:
    self.addNode(self.tail.pre, self.tail, val)

在链表中的第index个节点之前添加值为val的节点。


xxxxxxxxxx
    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        if index < 0:
            index = 0
        node = self.getNode(index)
        self.addNode(node.pre, node, val)

删除数据

如果索引index有效，则删除链表中的第index个节点


xxxxxxxxxx
def deleteAtIndex(self, index: int) -> None:
    if index < 0 or index >= self.size:
        return
    p = self.getNode(index)
    p.pre.next = p.next
    p.next.pre = p.pre
    self.size -= 1

线性结构_双向链表_增加节点数据线性结构_栈_栈的设计与实现

北京市昌平区回龙观镇南店村综合商业楼2楼226室