数据结构与算法的Python实现(三)——线性表之链表

上一篇中我提到线性表的另一种实现——链表,这一篇就主要讲链表。

一、链表的概念和基本思想

(一)链表的概念

线性表的一个基本特性就是元素的序列关系,顺序表虽然没有直接指明序列关系,但因为保存在了连续的存储空间内,所以形成了这种关系。我们也可以不把元素连续存储,而在每个元素中指明序列关系,这样就也可以实现线性表了,基于这种链接结构的线性表,就叫做链表。

(二)实现链表的基本思想

1.表中的每一个元素都独立存储在自己的一块空间内;

2.表中的任意元素都记录了下一元素的位置,可以通过这个位置找到下一元素。

由此,只需要找到第一个元素所在结点,就可以顺着链接找到任意一个元素所在结点。

二、单链表

(一)单链表的概念

单链表全称单向链接表,一般说链表就是指单链表。

单链表的每一个结点都是一个二元组,分别存放表的元素elem和下一结点next。表里的所有元素通过链接形成单链表,通过变量p找到首结点,顺次就可以找到其他元素。

所以说,只需要用一个变量保存对首结点的引用,就可以完全控制整个表了,这个变量就叫表头变量。

链表的最后一个结点并没有下一个元素,所以链接指向None(Python中的系统变量,表示空)。

由以上讨论,我们可以定义一个简单的表结点类:

class LNode:

def __init__(self,elem,next_node = None):

self.elem = elem

self.next = next_node

(二)链表操作

1.创建一个空链表

只需要把表头变量设置为None即可。O(1)

2.删除链表

同理,直接将表头变量指向None,解释器会自行回收被抛弃的结点。O(1)

3.判断是否为空

判断表头变量是否为None即可。O(1)

(三)元素操作

1.插入元素

•在表的首结点前插入O(1)

分为三个步骤,一是创建一个表结点q,二是将q的next指向第一个结点,即head当前指向的结点,然后将head指向q:

q = LNode(12)

q.next = head

head = q

•在其他位置插入O(n)

假设要插入的位置的前一结点为pre,操作类似:

q = LNode(12)

q.next = pre.next

pre.next = q

2.删除元素

•删除首结点元素O(1)

直接表头变量指向第二个结点即可:

head = head.next

•其他结点删除O(n)

同理,只需将上一结点跳过该结点指向下一结点即可:

3.扫描和遍历

•扫描定位O(n)

单链表的特性导致只能从首结点开始寻找制定结点,如果是按照下标i查找:

p = head

while p is not None and i>0:

i -= 1

p = p.next

如果是按照元素elem查找:

p = head

while (p is not None) and (not (p.elem == elem)):

p = p.next

•遍历O(n)

以遍历输出元素为例:

p = head

while p is not None:

print(p.elem)

p = p.next

4.求表的长度

采用遍历结点的方式:O(n)

def length(head):

p , n = head , 0

while p is not None:

n += 1

p = p.next

return n

这种方式效率比较低,每次求表长都需要遍历,我们可以在首结点前加一个结点作为存放表长度的区域,该结点的next指向第一个表结点,这样只需读取该区域就可以获取长度了,时间复杂度变为O(1),但每次执行插入删除时都需要修改改长度的值。

三、单链表的Python实现

先定义一个异常类用于处理空表访问等异常情况:

class LinkedListUnderflow(ValueError):

pass

在前面,我们定义了单链表结点类:

class LNode:

def __init__(self,elem,next_node = None):

self.elem = elem

self.next = next_node

接下来是单链表类的实现:

class LList:

def __init__(self): #创建空链表

self._head = None

def is_empty(self): #判断是否为空链表

return self._head is None

def prepend(self,elem): #在最开始插入元素

self._head = LNode(elem,self._head)

def pop(self): #弹出首结点元素并输出

if self._head is None:

raise LinkedListUnderflow(“pop None”)

e = self._head.elem

self._head = self._head.next

return e

def append(self,elem): #在最后追加元素

if self._head is None:

self._head = LNode(elem)

p = self._head

while p.next is not None:

p = p.next

p.next = LNode(elem)

def pop_last(self): #弹出尾结点元素并输出

if self._head is None:

raise LinkedListUnderflow(“pop_last None”)

p = self.head

if p.next is None:

e = p.elem

self._head = None

return e

while p.next.next is not None:

p = p.next

e = p.next.elem

p.next = None

return e

def find(self,pred): #找到第一个满足谓词pred的元素并输出

p = self._head

while p is not None:

ifpred(p.elem):

return p.elem

p = p.next

return None

def print(self): #依次输出全部元素

p = self._head

while p is not None:

print(p.elem, end =‘’)

if p.next is not None:

print(‘,’,end = ‘’)

p = p.next

print(‘’)

def for_each(self, proc): #遍历所有结点并执行proc操作

p = self._head

while p is not None:

proc(p.elem)

p = p.next

def elements(self): #按所有元素构造生成器

p = self._head

while p is not None:

yield p.elem

p = p.next

def filter(self,pred): #构造链表中符合谓词pred的元素的生成器

p = self.head

while p is not None:

if pred(p.elem):

yield p.elem

p = p.next

四、链表的其他形式

(一)单链表的拓展

单链表对于尾端的操作效率很低,如果用一个变量引用尾结点,那尾结点的相关操作时间复杂度就变为了O(1),可以用继承的方式来定义:

class LList2(LList):

def __init__(self):

LList.__init__(self)

self._rear = None

只需要在初始化时额外定义一个变量指向尾部,同样在部分操作时,需要重载方法,以最后插入元素为例:

def append(self,elem):

if self._head is None:

self._head = LNode(elem)

self._rear = self._head

else:

self._rear.next = LNode(elem)

self._rear = self._rear.next

(二)循环单链表

循环单链表的尾结点的next指向头结点,形成了一个圈,此时只需要一个rear指向尾结点就可以确保,首结点和尾结点的操作时间复杂度都为一,定义如下:

class LCList:

def __init__(self):

self._rear = None

部分操作会变简单,以在最后插入元素为例:

def append(self,elem):

p = LNode(elem)

if self._rear is None:

self._rear = p

p.next = p

else:

p.next = self._rear.next

self._rear.next = p

self._rear = self._rear.next #在开头插入时,删除这条语句即可

(三)双向链表

单循环链表存在的问题是删除尾结点的时间复杂度依然为O(n),如果在每个结点中,不仅可以引用下一个结点,还可以引用上一个结点的话,那这个问题就解决了,不过增加了额外的空间消耗。新的结点定义如下:

class DLNode(LNode):

def __init__(self,elem,pre = None,next_node = None):

LNode.__init__(self,elem,next_node)

self.prev = pre

双向链表的类可以直接从拓展后的单链表继承,具体操作要有变化,以删除尾结点为例:

def pop_last(self):

if self._head is None:

raise LinkedListUnderflow(“DLList pop_last None”)

e = self._rear.elem

self._rear = self._rear.pre

if self._rear is None:

self._head = None

else:

self._rear.next = None

return e

(四)循环双链表

循环双链表只需要把最后一个结点的next指向首结点即可,在此不做赘述,使用循环双链表,保存首或尾的引用,都可以保证首位的增删操作时间复杂度尾O(1)。

思考:顺序表和链表完成翻转和排序操作分别应该如何实现呢?下一篇讲表的应用,讲三个内容,一个是表的翻转,一个是表的排序,一个是Josephus问题的几种解法。

以下是上篇思考题我的实现,核心思想是使用两个栈,一个维护数据,一个维护最小值,用一倍的空间将getMin方法时间复杂度变为O(1),欢迎提建议:

class MyList:

def __init__(self):

self._list = [ ]

self._min_list = [ ]

def pop(self):

if self._list is None:

return None

self._min_list.pop()

return self._list.pop()

def push(self,x)

self._list.append(x)

if self._min_list is None:

self._min_list.append(x)

else:

self._min_list.append(min(x,self._min_list[-1]))

def top(self):

if self._list is None:

return None

return self._list[-1]

def getMin(self)

if self._min_list is None:

return None

return self._min_list[-1]

以上。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180618G0M0YW00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券