Python中双向链表的框架实现

发表于 | 分类于 | 阅读次数

这篇文章记录的是leetcode上的一道题目，从头实现一个链表，考察的比较全面，如果都实现处理，那么leetcode 上关于链表的简单类型题目应该秒懂。

Python中的链表

单向链表

|data|next| |:—:|:—:|

双向链表

|pre|data|next| |:—:|:—:|:—:|

  链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

双向链表实现

主要是在刷leetcode链表类题目时遇到的题目，感觉这样的题目挺不错的，考察的知识点比较系统，特此记录。

实现双向链表数据结构

1
2
3
4
5
class ListNode():
    def __init__(self,val):
        self.val = val
        self.next = None
        self.pre = None

链表类的主体结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyLinkedList(object):

    def __init__(self):
        
    def get(self, index):
        
    def addAtHead(self, val):

    def addAtTail(self, val):

    def addAtIndex(self, index, val):    
          
    def deleteAtIndex(self, index):     
      
    def printList(self):
  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
  • printList(self)：自己定义的，用来debug。
1
2
3
4
5
6
7
def __init__(self):
    """
    Initialize your data structure here.
    """
    self.start = None
    self.listLegth=0
    self.end = None

我这里定义了两个节点索引标识，用来指示链表的头部和尾部，另外还定义了一个链表长度变量，在查询、插入和删除时用来判断index是否有效。

1
2
3
4
5
6
7
def get(self, index):
    temp = self.start
    if index>=self.listLegth or self.listLegth==0:
        return -1
    for i in xrange(index):
        temp = temp.next
    return temp.val

这个函数是用来获取指定索引处的值，ok，那我们主要来讨论特殊情况：

  • index大于等于链表长度，那肯定是无效的，直接返回-1。
  • 当前链表长度为0时，你查询肯定是无效的，直接返回-1。
1
2
3
4
5
6
7
8
9
10
def addAtHead(self, val):
    start = ListNode(val)
    start.next = self.start
    if self.start: #当之前没有头部时，不需要设置pre的指向
        self.start.pre = start
    start.pre = None
    self.start = start
    if not self.end:
        self.end = self.start
    self.listLegth+=1

这个函数是用来为链表头部增加一个节点，这里要注意一点的是，当你添加头部时，需要判断当前链表有没有尾部，如果没有，同时也要初始化尾部。为什么？因为只要你的链表有节点存在，那么头部和尾部一定也同时存在。这在添加尾部的函数里面一样需要注意这个问题。

1
2
3
4
5
6
7
8
9
10
def addAtTail(self, val):
    if not self.end:
        self.addAtHead(val)
    else:
        end = ListNode(val)
        self.end.next = end
        end.pre = self.end
        end.next = None
        self.end = end
        self.listLegth+=1

这里先判断self.end是否指向节点，其实就是判断链表是否为空，若为空，则直接调用self.addAtHead()，效果一样，若不为空，则添加新的尾部，注意这里的链表是双向链表，next和pre都需要设置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def addAtIndex(self, index, val):
    if index==self.listLegth:
        self.addAtTail(val)
    elif self.listLegth==0 and index>=1:
        pass 
    elif index<self.listLegth:
        temp = self.start
        for i in xrange(index):
            temp = temp.next
        before = temp.pre
        new_list = ListNode(val)
        new_list.pre = before
        before.next = new_list
        new_list.next = temp
        temp.pre = new_list
        self.listLegth+=1

我们先考虑特殊情况：

  • 如果index等于当前链表长度，则等同于添加一个尾部。
  • 如果当前链表为空时，若index==0，相当于添加一个头部。
  • 如果当前链表为空，index>=1，则是非法的，不做任何动作。

步骤很直观，先循环到需要添加的位置，生成一个新的节点，然后设置好新节点的pre和next属性就OK了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def deleteAtIndex(self, index):
    if self.listLegth==0:
        pass
    elif index<self.listLegth:
        temp = self.start
        for i in xrange(index):
            temp = temp.next
        if not temp.next:
            temp.pre.next = None
            self.end = temp.pre
        elif not temp.pre:
            temp.next.pre = None
            self.start = temp.next
        else:
            temp.pre.next = temp.next
            temp.next.pre = temp.pre
        self.listLegth-=1

特殊情况：

  • 当前链表为空时，不做动作。
  • index大于等于self.listLegth，此时不做动作。
  • 当此时删除的节点为头部时，我们还要更新一下self.start。
  • 当此时删除的节点为尾部时，我们还要更新一下self.end。

循环到制定的index处，断开需要删除的节点，将删除节点和前面和后面的节点进行连接，注意双向链表需要设置pre和next。

相关题目- 203. 删除链表中的节点，237. 删除链表中的节点

1
2
3
4
5
6
7
def printList(self):
    temp = self.start
    out_array=[]
    while temp:
        out_array.append(temp.val)
        temp = temp.next
    print(out_array)

从self.start遍历到self.end，将所有值储存在列表中，最后输出。