为什么需要链表

数组的底层原理是顺序存储，是一块连续的内存空间，有了这块内存空间的首地址，就能直接通过索引计算出任意位置的元素地址。

链表不一样，一条链表并不需要一整块连续的内存空间存储元素。链表的元素可以分散在内存空间的天涯海角，通过每个节点上的next, prev 指针，将零散的内存块串联起来形成一个链式结构。

这样做的好处很明显，首先就是可以提高内存的利用效率，链表的节点不需要挨在一起，给点内存 new 出来一个节点就能用，操作系统会觉得这娃好养活。

可以抽象为一条弯曲的链子，通过一个个环连接在一起。

另外一个好处，它的节点要用的时候就能接上，不用的时候拆掉就行了，从来不需要考虑扩缩容和数据搬移的问题，理论上讲，链表是没有容量限制的（除非把所有内存都占满，这不太可能）。

当然，不可能只有好处没有局限性。数组最大的优势是支持通过索引快速访问元素，而链表就不支持。

这个不难理解吧，因为元素并不是紧挨着的，所以如果你想要访问第 3 个链表元素，你就只能从头结点开始往顺着 next 指针往后找，直到找到第 3 个节点才行。

单链表

链表的创建

class Listnode:
    def __init__(self, x):
        self.val = x
        self.next = None


def create_linked_list(nums):
    head = Listnode(nums[0])
    cur = head
    for i in range(1, len(nums)):
        cur.next = Listnode(nums[i])
        cur = cur.next
    return head


def print_linked_list(current_node):
    while current_node:
        print(current_node.val, end='->')
        current_node = current_node.next
    print('None')


if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
    linked_list = create_linked_list(nums)
    print_linked_list(linked_list)

最终的输出结果：1->2->3->4->5->None

链表的实现

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None


class MyLinkedList(object):

    def __init__(self):
        self.size = 0
        self.head = ListNode(0)

    def get(self, index):
        """
        从链表中获取指定位置的元素值。
        :param index: 要获取元素的位置索引，从0开始计数。
        :type index: int
        :return: 如果索引有效，则返回对应位置的元素值；否则返回-1。
        :rtype: int
        """
        # 检查索引是否超出链表范围
        if index < 0 or index >= self.size:
            return -1
        cur = self.head
        # 遍历链表至指定索引位置
        for _ in range(index + 1):
            cur = cur.next
        return cur.val  # 返回指定位置的元素值

    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.addAtIndex(0, val)

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index, val):
        """
        在指定索引处插入一个新节点。

        :param index: 要插入节点的索引位置。如果索引大于当前链表长度，则不做任何操作；
                      如果索引小于0，则将节点插入到链表开头。
        :param val: 要插入的节点的值。
        :return: None
        """
        if index > self.size:  # 如果索引大于链表长度，则直接返回，不做任何操作
            return
        if index < 0:  # 如果索引小于0，将节点插入到链表开头
            index = 0
        self.size += 1  # 更新链表大小
        pre = self.head
        # 定位到要插入节点的前一个节点
        for _ in range(index):
            pre = pre.next  # 逐个遍历，找到正确的位置
        to_add = ListNode(val)  # 创建新节点
        to_add.next = pre.next  # 新节点指向pre节点的next节点
        pre.next = to_add  # pre的next指向新节点

    def deleteAtIndex(self, index):
        """
        从链表中删除指定索引的元素。

        :param index: 要删除的元素的索引。如果索引无效（小于0或大于等于链表长度），则不进行任何操作。
        :type index: int
        :return: None
        """
        if index < 0 or index >= self.size:
            return
        self.size -= 1
        pre = self.head
        # 移动到要删除节点的前一个节点
        for _ in range(index):
            pre = pre.next
        # 要删除节点的前一个节点next指向删除节点的后一个节点
        pre.next = pre.next.next

双链表

链表的创建

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None


def create_double_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        node = ListNode(arr[i])
        cur.next = node
        node.prev = cur
        cur = cur.next
    return head


def print_double_linked_list(head):
    while head:
        print(head.val, end='->')
        head = head.next


if __name__ == '__main__':
    head = create_double_linked_list([1, 2, 3, 4, 5])
    print_double_linked_list(head)

链表的实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
        self.prev = None


class MyLinkedList:

    def __init__(self):
        self.size = 0
        self.head, self.tail = ListNode(0), ListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, index: int) -> int:
        """
        从链表中获取指定位置的元素值。
        """
        # 检查索引是否超出链表范围
        if index < 0 or index >= self.size:
            return -1
        # 选择从头结点还是尾结点开始遍历取决于索引的位置，以优化遍历效率
        # 以索引值作为分割，左边短就从头结点开始遍历，右边短就从尾结点开始遍历
        if index + 1 < self.size - index:
            curr = self.head
            # 遍历链表到达指定索引位置
            for _ in range(index + 1):
                curr = curr.next
        else:
            curr = self.tail
            # 遍历链表到达指定索引位置
            for _ in range(self.size - index):
                curr = curr.prev
        # 遍历链表到达指定索引位置
        return curr.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        """
        在双向链表的指定位置插入一个新节点，并保持双向链表的有序。
        """
        # 处理index大于链表长度的情况，直接返回不进行操作
        if index > self.size:
            return
        # 将负索引调整为0
        if index < 0:
            index = 0

        # 确定插入位置的前驱节点和后继节点
        if index < self.size - index:
            # 当index在链表前半部分时，正常计算前驱节点和后继节点
            pred = self.head
            for _ in range(index):
                pred = pred.next
            succ = pred.next
        else:
            # 当index在链表后半部分时，从尾部向前计算前驱节点和后继节点
            succ = self.tail
            for _ in range(self.size - index):
                succ = succ.prev
            pred = succ.prev

        # 更新链表大小
        self.size += 1
        # 创建新节点并插入到链表中
        to_add = ListNode(val)
        to_add.next = succ
        to_add.prev = pred
        pred.next = to_add
        succ.prev = to_add

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        if index < self.size - index:
            # 当index在链表前半部分时，正常计算前驱节点和后继节点
            pred = self.head
            for _ in range(index):
                pred = pred.next
            succ = pred.next.next
        else:
            # 当index在链表后半部分时，从尾部向前计算前驱节点和后继节点
            succ = self.tail
            for _ in range(self.size - index - 1):
                succ = succ.prev
            pred = succ.prev.prev
        self.size -= 1
        pred.next = succ
        succ.prev = pred