[数据结构与算法]如何优雅地实现链表及相关链表题实现

链表总结

• 单链表
• 循环链表
• 双向链表

链表的特点：

• 由一个个节点 Node(data, next, prev) 组成。其中 next, prev 分别为指向下一个节点的指针，data 表示存储的数据。
• 链表是由一个个不连续的空间组成，由指针将零散的内存块串联在一起，因此比较节省空间(相较于 array)
• 链表适合于内存少，插入、删除频繁的使用场景。
• 链表不适用于查询频繁的使用场景
• 对于无序的链表，插入、删除操作时间复杂度为 O(1)。查找时间复杂度为 O(n)
• 对于有序的链表，插入、删除时间复杂度为 O(n)。查找时间复杂度为 O(n)
• 链表可以通过双向链表实现查询优化，记录上一次查询的位置，待下一次查询到来时，判断向前或者向后查找。

链表实现总结

• 理解指针，即指向某个变量的内存地址，通过指针引用即可找到相关变量
• 内存泄漏或者进行插入指针丢失

在进行插入或者删除操作时，避免指针丢失，或者循环指向的问题：例如:
cur.next = node
node.next = cur
以上由于 cur 的前一个指针出现自己指向自己，更多情况需要自己反复调试

• 使用哨兵优化

对于整个链表来说，self.head表示头节点，也是存储整个链表的数据。在查询操作或者插入操作时，需要找到相关节点。
可以采用 cur = self.head。cur = cur.next 等来优化代码逻辑。

• 重点注意边缘条件

对于操作链表来说，一般包含三种情况：1. 链表为空的情况。2. 链表只有一个节点的情况。3. 链表有多个节点的情况。
对于插入，删除来说。需要分情况讨论。避免 cur.next 或者 cur.prev 进行指向时出现 NoneType。需要灵活应对。

链表相关算法题

• 快慢指针判断是否为环状链表
• 反转链表
• 有序链表的合并
• 删除指定位置的 Node

实现

单链表

# 单链表
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class SingleChain:
    """
    单链表的实现
    """

    def __init__(self):
        self._head = None

    def add(self, data):
        """
        链表头添加元素
        :param data:
        :return:
        """
        node = Node(data)
        if self._head is None:
            self._head = node
        else:
            node.next = self._head
            self._head = node

    def append(self, data):
        """
        链表尾部添加元素
        :param data:
        :return:
        """
        node = Node(data)
        if self._head is None:
            self._head = node
        else:
            cur = self._head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def insert(self, index, data):
        """
        插入链表指定位置, index 分为三种情况：负数，位于 0-len(listNode), 大于链表长度
        :param data:
        :return:
        """
        cur, pre = None, None
        if index <= 0:
            self.add(data)
        elif index > self.__len__():
            self.append(data)
        else:
            count = 0
            node = Node(data)
            cur = self._head
            while count < index:
                pre = cur
                cur = cur.next
                count += 1

            pre.next = node
            node.next = cur

    def find(self, data):
        """
        找到第一个链表中的数据
        :param data:
        :return: index
        """
        if self._head is None:
            return False

        cur = self._head
        index = 0
        while cur is not None:
            if cur.data == data:
                return index

            index += 1
            cur = cur.next

        return False

    def remove(self, data):
        cur = self._head
        if cur is None:
            return

        pre = None
        while cur is not None:
            if cur.data == data:
                pre.next = cur.next
            pre = cur
            cur = cur.next

    def travel(self):
        cur = self._head
        while cur is not None:
            print("-**{}".format(cur.data), end='')
            cur = cur.next
        print()

    def __len__(self):
        count = 0
        cur = self._head
        while cur is not None:
            count += 1
            cur = cur.next
        return count

环状链表

from chain.single_chain import SingleChain
from chain.single_chain import Node


# 循环链表
class CircleLink(SingleChain):
    def __init__(self):
        super(CircleLink, self).__init__()
        self._head = None

    def add(self, data):
        node = Node(data)
        if self._head is None:
            node.next = node
            self._head = node
        else:
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            node.next = self._head
            self._head = node
            cur.next = node

    def append(self, data):
        node = Node(data)
        if self._head is None:
            node.next = self._head
            self._head = node
        else:
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            node.next = self._head
            cur.next = node

    def travel(self):
        cur = self._head
        while cur.next != self._head:
            print("-**{}".format(cur.data), end='')
            cur = cur.next
        print("-**{}".format(cur.data), end='')  # 由于是 cur.next 判断的，故 cur 指向最后一个节点
        print()

    def find(self, data):
        if self._head is None:
            return False

        cur = self._head
        index = 0
        while cur.next != self._head:
            if cur.data == data:
                return index
            index += 1
            cur = cur.next
        if cur.data == data:  # 最后一个
            return self.__len__()

        return False

    def remove(self, data):
        cur = self._head
        if cur.next == self._head:
            self._head = None
            return

        pre = None
        while cur.next != self._head:
            if cur.data == data:
                pre.next = cur.next
                return
            pre = cur
            cur = cur.next

        # 退出循环, cur指向尾结点
        if cur.data == data:
            # 链表中只有一个结点
            pre.next = self._head
            return

    def __len__(self):
        count = 0
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count + 1  # 未计算最后一个 Node

双向链表

from chain.single_chain import SingleChain


# 双向链表
class XNode(object):
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


# 双向链表
class DoubleLink(SingleChain):
    def __init__(self):
        super(DoubleLink, self).__init__()
        self._head = None

    def add(self, data):
        node = XNode(data)
        if self._head is None:
            self._head = node
            return
        else:
            node.next = self._head
            self._head.prev = node
            self._head = node
            return

    def append(self, data):
        node = XNode(data)
        if self._head is None:
            self._head = node
            return
        else:
            cur = self._head
            while cur.next is not None:
                cur = cur.next

            cur.next = node
            node.prev = cur
            return

    def insert(self, index, data):
        if index < 0:
            self.add(data)
            return

        elif index >= self.__len__():
            self.append(data)
            return

        else:
            # status 1: 空
            cur = self._head
            if cur is None:
                self.add(data)
                return

            # status 2: 只有一个节点
            if cur.next is None:
                if index <= 0:
                    self.add(data)
                    return
                if index >= self.__len__():
                    self.append(data)
                    return

            # status 多个节点
            else:
                count = 0
                node = XNode(data)
                cur = self._head
                while count < index:
                    cur = cur.next
                    count += 1

                node.next = cur
                node.prev = cur.prev
                cur.prev.next = node
                cur.prev = node

有序双向链表

from chain.double_direction_chain import DoubleLink
from chain.double_direction_chain import XNode


# 有序双向链表，记录上一次的查找的 pos, 决定向前还是向后查找
class OrderLink(DoubleLink):
    def __init__(self):
        super(DoubleLink, self).__init__()
        self._head = None
        self._pos = None
        self._find_node = None

    def add(self, data):
        node = XNode(data)
        # status 1: 链表为空
        if self._head is None:
            self._head = node
            return

        # status 2: 链表只有一个节点
        if self._head.next is None:
            # 插入数据大于该节点, 直接在尾部插入
            if self._head.data <= data:
                node.prev = self._head
                self._head.next = node
                return

            else:
                # 否则直接在首部插入
                node.next = self._head
                self._head.prev = node
                self._head = node
                return

        # status 3: 链表有多个节点
        else:
            cur = self._head
            tail = self.tail()
            if data >= tail.data:
                # 尾部加入
                tail.next = node
                node.prev = tail
                return

            while cur.next is not None and data > self._head.data:
                # 找到对应节点
                cur = cur.next

            if cur == self._head:
                # 首部插入
                node.next = self._head
                self._head.prev = node
                self._head = node
                return

            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node
            return

    def find(self, data):
        cur = self._head
        if cur is None:
            return
        if self._find_node:
            _cur = self._find_node
            if data >= self._find_node.data:
                # 向后查找
                pos = self._pos
                while _cur is not None:
                    if data == _cur.data:
                        self._pos = pos
                        self._find_node = _cur
                        return pos
                    _cur = _cur.next
                    pos += 1
            else:
                # 向前查找
                pos = self._pos
                while _cur is not None:
                    if data == _cur.data:
                        self._pos = pos
                        self._find_node = _cur
                        return pos

                    _cur = _cur.prev
                    pos -= 1

        else:
            # 遍历查找
            pos = 0
            while cur is not None:
                if data == cur.data:
                    self._pos = pos
                    self._find_node = cur
                    return pos
                cur = cur.next
                pos += 1

    def travel(self):
        cur = self._head

        while cur.next is not None:
            print("-**{}".format(cur.data), end='')
            cur = cur.next
        print("-**{}".format(cur.data), end='')  # 由于是 cur.next 判断的，故 cur 指向最后一个节点
        print()

    def tail(self):
        cur = self._head
        while cur.next is not None:
            cur = cur.next

        return cur

    def obtain_head(self):
        return self._head

源码

链表实现

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系