Violin's Blog
0%

链表(下)

发表于 分类于 本文字数： 6.1k 阅读时长 ≈ 15 分钟

链表这块知识理解起来简单，代码实现起来，容易出错，谁写谁知道，所以就有了链表(下)。

写链表代码的技巧

理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针里存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

指针，英文定义，A pointer is a variable whose value is the address of another variable.

警惕指针丢失和内存泄漏

比如，在a、b两个结点之间插入一个结点c，一定是先执行c->next=a->next，先把结点c指向结点b，然后再将结点a指向结点c，即a->next=c。如果顺序颠倒了，就会造成结点b的丢失，链表分成了两半，进而造成内存泄漏。因此，在插入结点时，一定要注意操作的顺序。

删除链表结点时，也一定要记得手动释放内存空间，否则也会出现内存泄漏的情况。当然，对于像Java这种虚拟机自动管理内存的编程语言来说，就不需要考虑那么多了。

利用哨兵简化实现难度

非哨兵模式下链表的插入，比如在p结点后插入一个新结点

1
2
3
4
5
# 正常情况
new_node.next = p.next
p.next = new_node
# 边界情况，比如向空链表中插入第一个结点
if (head == None){head = new_node}

非哨兵模式下链表的删除，比如删除结点p的后继结点

1
2
3
4
# 正常情况
p.next = p.next.next
# 边界情况，比如删除最后一个结点
p.next = None

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。

为了解决边界问题，引入哨兵结点。

哨兵结点，结点本身不存储数据，指定链表头结点，称为新的头结点，如图所示，

带有哨兵结点的链表叫带头链表；没有哨兵结点的链表叫做不带头链表。

因为哨兵结点一直存在，所以插入第一个节点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑。

不信的话，自己画画图，理解一下代码，发现确实是真的耶

重点留意边界条件处理

检查链表代码是否正确的边界条件有这样几个：

  • 如果链表为空时，代码是否能正常工作
  • 如果链表只包含一个结点时，代码是否能正常工作
  • 如果链表只包含两个结点时，代码是否能正常工作
  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作

举例画图，辅助思考

举例法和画图法

多写多练，没有捷径

5个常见的链表操作

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第n个结点
  • 求链表的中间结点

其实除了两个有序的链表合并，其余的在链表上(上)都写过了，总结起来就是1.快慢指针2.反转相邻的结点。上节课后思考判断回文串这一道题目就把这两个知识点都考查到了，简直是妙啊！

课后思考

哨兵模式在其他场景上的应用。

暂时没想到，后续用到了再来补充吧=.=

合并两个有序链表

遍历实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def merge_sorted_list(l1: Node, l2: Node):
    """
        合并两个有序链表
        时间复杂度O(m)+O(n)
    :param l1: 链表1头结点
    :param l2: 链表2头结点
    :return: 合并后链表的头结点
    """
    node = Node(data=-1)
    # 需要一个变量保存头结点
    head = node
    while l1 and l2:
        if l1.data <= l2.data:
            node.next = l1
            # 后移链表1结点
            l1 = l1.next
        else:
            node.next = l2
            # 后移链表2结点
            l2 = l2.next
        node = node.next

    # 合并 未合并完的链表
    node.next = l1 if l1 else l2
    return head.next
  
  
if __name__ == '__main__':
    s = SingleLinkedList()

    s.insert_to_head(5)
    s.insert_to_head(3)
    s.insert_to_head(1)

    p = SingleLinkedList()
    p.insert_to_head(6)
    p.insert_to_head(5)
    p.insert_to_head(4)
    p.insert_to_head(3)

    q = merge_sorted_list(s.get_head_node(), p.get_head_node())

递归实现

代码先放到这，等学完递归在回过头来看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge_sorted_list2(l1: Node, l2: Node):
    """
        合并两个有序链表
        主要思路：
        	list1[0] + merge(list1[1], list2[0]) 当list1[0]<list2[0]
          list2[0] + merge(list1[0], list2[1]) otherwise
    :param l1: 链表1头结点
    :param l2: 链表2头结点
    :return: 合并后链表的头结点
    """
    if not l1:
        return l2

    if not l2:
        return l1

    if l1.data <= l2.data:
        l1.next = merge_sorted_list(l1.next, l2)
        return l1
    else:
        l2.next = merge_sorted_list(l1, l2.next)
        return l2

LRU缓存算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Node:
    def __init__(self, x, y):
        self.key = x
        self.value = y
        self.next = None
        self.prev = None


class LRUCache(object):

    def __init__(self, capacity: int):
        self.cap = capacity
        # 存储key和node
        self.hkeys = {}
        # 哨兵结点 避免考虑边界问题
        self.top = Node(None, -1)
        self.tail = Node(None, -1)

        self.top.next = self.tail
        self.tail.prev = self.top

    def get(self, key: int) -> int:
        if key in self.hkeys.keys():
            # 1.获取结点
            cur = self.hkeys[key]
            # 2.从当前位置拿出
            cur.prev.next = cur.next
            cur.next.prev = cur.prev
            # 3.放到链表头部
            # 3.1 保存top后面的结点
            tmp = self.top.next
            # 3.2 top和cur绑定
            self.top.next = cur
            cur.prev = self.top
            # 3.3 cur和tmp绑定
            cur.next = tmp
            tmp.prev = cur
            return self.hkeys[key].value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hkeys.keys():
            # 1.获取结点
            cur = self.hkeys[key]
            # 修改value值
            cur.value = value
            # 2.跳出原位置
            cur.prev.next = cur.next
            cur.next.prev = cur.prev
            # 3.将cur放到头结点
            top_node = self.top.next
            self.top.next = cur
            cur.prev = self.top
            cur.next = top_node
            top_node.prev = cur
        else:
            if len(self.hkeys.keys()) > self.cap:
                # 从哈希表删除key
                self.hkeys.pop(self.tail.prev.key)
                # 去掉了后继指针
                self.tail.prev.prev.next = self.tail
                # 修改尾结点前驱指针，self.tail.prev.prev有点懵的
                self.tail.prev = self.tail.prev.prev

            # 新增结点
            cur = Node(key, value)
            self.hkeys[key] = cur
            # 最近用过的放到链表头部
            """
                我第一次写的
                cur.next = self.top.next
                self.top.prev = cur
    
                self.top.next = cur
                cur.prev = self.top
            """
            # 利用tmp保留top下一个结点
            tmp = self.top.next  
            cur.next = tmp
            tmp.prev = cur

            self.top.next = cur
            cur.prev = self.top

感受

  1. 写起来好像也没想象中那么难，可能是因为用到哨兵结点，不需要考虑边界问题。

  2. 主要操作包括：结点从当前位置取出、头部插入结点。

  3. 操作之间不需要考虑先后顺序，比如结点跳出原位置，

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # 结点跳出原位置
    cur.next.prev = cur.prev
    cur.prev.next = cur.next

    # 链表头部插入结点
    tmp = self.top.next
    cur.next = tmp
    tmp.prev = cur

    self.top.next = cur
    cur.prev = self.top

    于是，为了验证这个观点，写一个简单的双向链表demo验证一下，无论怎么更换insert_node_from_head()方法中后四行代码的顺序，结果都是一样的。如果有不对的地方，欢迎指教哈=。=

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    class Node:
      
        def __init__(self, value):
            self.value = value
            self.next = None
            self.prev = None


    class TwoWayLoop(object):

        def __init__(self):
            self.top = Node(value=-1)
            self.tail = Node(value=-1)

            self.top.next = self.tail
            self.tail.prev = self.top

        def insert_node_from_head(self, value):
            node = Node(value=value)

            tmp = self.top.next

            tmp.prev = node
            node.prev = self.top
            self.top.next = node
            node.next = tmp

        def delete_node(self, value):
            """
                暂时没想好怎么写
            :return: 
            """
            node = self.top.next

            while node.next:
                pass

        def print_all(self):
            node = self.top.next

            while node.next:
                print(node.value)
                node = node.next


    if __name__ == '__main__':
        t = TwoWayLoop()

        t.insert_node_from_head(4)
        t.insert_node_from_head(3)
        t.insert_node_from_head(2)
        t.insert_node_from_head(1)

        t.print_all()  # 1->2->3->4

附：获取类对象的私有属性

在合并两个有序链表中，需要获取链表的头结点。上篇文章代码中，单链表的SingleLinkedList中的头结点初始化时定义为私有属性self.__head=None，如果直接通过实例对象获取__head会抛出AttributeError异常。

1
2
3
4
5
6
7
8
9
class SingleLinkedList(object):
  
  def __init__(self):
    self.__head = None
    
if __name__ == '__main__':
  s = SingleLinkedList()
  s.insert_to_head(1)
  print(s.__head)  # AttributeError: 'SingleLinkedList' object has no attribute '__head'

正确的打开方式

  1. 通过定义一个方法获取私有属性
1
2
3
4
5
6
7
8
9
10
11
12
class SingleLinkedList(object):
  
  def __init__(self):
    self.__head = None
    
  def get_head_node(self):
    return self.__head
    
if __name__ == '__main__':
  s = SingleLinkedList()
  s.insert_to_head(1)
  print(s.get_head_node().data)  # 1
  1. 通过property将方法转化为属性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SingleLinkedList(object):
  
  def __init__(self):
    self.__head = None
    
  def get_head_node(self):
    return self.__head

  head = property(get_head_node)
  
  
if __name__ == '__main__':
  s = SingleLinkedList()
  s.insert_to_head(1)
  print(s.head.data)  # 1
  1. 通过property装饰器
1
2
3
4
5
6
7
8
9
10
11
12
13
class SingleLinkedList(object):
  
  def __init__(self):
    self.__head = None
   
  @property
  def head(self):
  	return self.__head
  
if __name__ == '__main__':
  s = SingleLinkedList()
  s.insert_to_head(1)
  print(s.head.data)  # 1

参考链接：

  1. python变量——单下划线和双下划线
  2. Python property() 函数
  3. 合并两个有序链表（python）
您的支持将鼓励我继续创作！