3.链表（python数据结构与算法学习）

系统管理员 2021-05-12 11:50 774阅读 0赞

### 为什么需要链表 ###

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

### 链表的定义 ###

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（**数据存储区+下个节点链接区**）里存放下一个节点的位置信息（**即地址**）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70]

## 3.1 单向链表 ##

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个**信息域**（元素域）和一个**链接域**。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70 1]

*  表元素域elem用来存放具体的数据。
 *  链接域next用来存放下一个节点的位置（python中的标识）
 *  变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

### 节点实现（对应上图中的结点） ###

class Node(object):
        """单链表结点"""
        def __init__(self, elem):
            self.elem = elem       # 存放元素
            self.next = None       # 指向下一个结点

### 单链表的操作（函数从简至繁） ###

*  is\_empty() 链表是否为空
 *  length() 链表长度
 *  travel() 遍历整个链表
 *  add(item) 链表头部添加元素
 *  append(item) 链表尾部添加元素
 *  search(item) 查找节点是否存在
 *  remove(item) 删除节点
 *  insert(pos, item) 指定位置添加元素

### 单链表的实现 ###

class SingleLinkList(object):
        """单链表"""
        def __init__(self, node=None):
            self.__head = node   # 初始化头结点的指向
    
        def is_empty(self):
            """链表是否为空"""
            return self.__head == None

#### 链表长度 ####

def length(self):
            """链表长度"""
            count = 0
            cur = self.__head
    
            while cur != None:
                count += 1
                cur = cur.next
            return count

#### 遍历整个链表 ####

def travel(self):
            """遍历整个链表"""
            cur = self.__head
            while cur != None:
                print(cur.elem)
                cur = cur.next

#### 链表头部添加元素 ####

![在这里插入图片描述][20200604103017603.png]

def add(self, item):
            """链表头部添加元素"""
            node = Node(item)
            node.next = self.__head   # 4行5行代码不可交换顺序
            self.__head = node

#### 链表尾部添加元素 ####

def append(self, item):
            """链表尾部添加元素"""
            node = Node(item)
            cur = self.__head
    
            if self.is_empty():   # 假如一开始链表就为空
                self.__head = node
            else:
                while cur.next != None:
                    cur = cur.next
                cur.next = node

#### 查找结点是否存在 ####

def search(self, item):
            """查找节点是否存在"""
            cur = self.__head
    
            while cur != None:
                if cur.elem == item:
                    return "该节点存在"
                else:
                    cur = cur.next
            return "该节点不存在"

#### 删除结点 ####

![在这里插入图片描述][2020060410302724.png]

def remove(self, item):
            """删除节点"""
            cur = self.__head
            pre = None
            while cur != None:
                if cur.elem == item:
                    if pre == None:    # 考虑链表只有一个结点，而且该结点正好需要删除
                        self.__head = cur.next
                    else:
                        pre.next = cur.next
                    return "节点已删除"
    
                else:
                    pre = cur
                    cur = cur.next
            return "该链表中不存在您想删除的节点"

#### 指定位置添加元素 ####

![在这里插入图片描述][2020060410303764.png]

def insert(self, pos, item):
            """指定位置添加元素"""
            if pos <= 0:
                self.add(item)
    
            elif pos >= self.length():
                self.append(item)
    
            else:
                count = 0
                cur = self.__head
                pre = None
    
                while count < pos:
                    pre = cur
                    cur = cur.next
                    count += 1
    
                node = Node(item)
                pre.next = node
                node.next = cur
                print("插入完成")

### 链表与顺序表的对比 ###

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示：

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th align="center">链表</th> 
   <th>顺序表</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>访问元素</td> 
   <td align="center">O(n)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>在头部插入/删除</td> 
   <td align="center">O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>在尾部插入/删除</td> 
   <td align="center">O(n)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>在中间插入/删除</td> 
   <td align="center">O(n)</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

**注意**：虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。**链表**的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。**顺序表**查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。

## 3.2 单向循环列表 ##

单链表的一个变形是单向循环链表，链表中最后一个结点的next域不再为None，而是指向链表的头结点。

![在这里插入图片描述][2020060410304850.png]

### 单向循环列表的操作（参考单链表） ###

*  is\_empty() 判断链表是否为空
 *  length() 返回链表的长度
 *  travel() 遍历
 *  add(item) 在头部添加一个节点
 *  append(item) 在尾部添加一个节点
 *  insert(pos, item) 在指定位置pos添加节点
 *  remove(item) 删除一个节点
 *  search(item) 查找节点是否存在

#### 实现： ####

class Node(object):
        """单向循环链表结点"""
        def __init__(self, elem):
            self.elem = elem
            self.next = None
    
    
    class SingleCycleLink(object):
        """单向循环链表"""
        def __init__(self, node=None):
            self.__head = node
            if node != None:
                node.next = self.__head
    
        def is_empty(self):
            """判断链表是否为空"""
            return self.__head == None
    
        def length(self):
            """返回链表的长度"""
    
            if self.is_empty():
                return 0
    
            count = 1
            cur = self.__head
            while cur.next != self.__head:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历"""
            if self.is_empty():
                print(None)
                return
    
            cur = self.__head
            while cur.next != self.__head:
    
                print(cur.elem)
                cur = cur.next
    
            print(cur.elem)
    
        def add(self, item):
            """在头部添加一个节点"""
            node = Node(item)
    
            if self.is_empty():
                self.__head = node
                node.next = self.__head
    
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node
            node.next = self.__head
            self.__head = node
    
        def append(self, item):
            """在尾部添加一个节点"""
            node = Node(item)
            if self.is_empty():
                self.__head = node
                node.next = self.__head
    
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node
            node.next = self.__head
    
        def insert(self, pos, item):
            """在指定位置pos添加节点"""
            if pos <= 0:
                self.add(item)
            elif pos >= (self.length()):
                self.append(item)
            else:
                cur = self.__head
                pre = None
                node = Node(item)
                count = 0
                while count < pos:
                    count += 1
                    pre = cur
                    cur = cur.next
                pre.next = node
                node.next = cur
    
        def remove(self, item):
            """删除一个节点"""
            if self.is_empty():
                print("链表为空")
                return
    
            pre = None
            cur = self.__head
    
            while cur.next != self.__head:
                # 头结点
                if cur == self.__head:
                    # 找到尾结点
                    end_cur = self.__head
                    while end_cur.next != self.__head:
                        end_cur = end_cur.next
    
                    if cur.elem == item:
                        self.__head = cur.next
                        end_cur.next = self.__head
                        return
    
                else: # 中间结点
                    if cur.elem == item:
                        pre.next = cur.next
                        return
    
                pre = cur
                cur = cur.next
    
            # 尾结点
            if cur.elem == item:
                if cur == self.__head:  # 链表只有一个结点
                   self.__head = None
                else:
                    pre.next = cur.next
    
        def search(self, item):
            """查找节点是否存在"""
            if self.is_empty():
                print("链表为空")
                return
            else:
                cur = self.__head
                while cur.next != self.__head:
                    if cur.elem == item:
                        print("该结点存在")
                        return
                    else:
                        cur = cur.next
                if cur.elem == item:
                    print("该结点存在")
                    return
            print("该结点不存在")

## 3.3 双向链表 ##

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

![在这里插入图片描述][20200604103108751.png]

### 双向链表的操作（参考单链表） ###

*  is\_empty() 链表是否为空
 *  length() 链表长度
 *  travel() 遍历链表
 *  add(item) 链表头部添加
 *  append(item) 链表尾部添加
 *  insert(pos, item) 指定位置添加
 *  remove(item) 删除节点

#### 实现： ####

class Node(object):
        """双链表结点"""
        def __init__(self, elem):
            self.elem = elem
            self.prev = None
            self.next = None
    
    
    class DoubleLinkList(object):
        """双链表"""
        def __init__(self, node=None):
            self.__head = node
    
        def is_empty(self):
            """链表是否为空"""
            return self.__head == None
    
        def length(self):
            """链表长度"""
            cur = self.__head
            count = 0
    
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            if self.is_empty():
                print("该链表为空。无法遍历")
            cur = self.__head
            while cur != None:
                print(cur.elem)
                cur = cur.next
    
        def add(self, item):
            """链表头部添加"""
            node = Node(item)
    
            if self.is_empty():
                self.__head = node
    
            else:
                node.next = self.__head
                self.__head.prev = node
                self.__head = node
    
        def append(self, item):
            """链表尾部添加"""
            node = Node(item)
            if self.is_empty():
                self.__head = node
    
            else:
                cur = self.__head
                while cur.next != None:
                    cur = cur.next
                cur.next = node
                node.prev = cur
    
        def insert(self, pos, item):
            """指定位置添加"""
            if pos <= 0:
                self.add(item)
            elif pos >= self.length():
                self.append(item)
    
            else:
                node = Node(item)
                count = 0
                cur = self.__head
                while count < pos:
                    count += 1
                    cur = cur.next
    
                node.next = cur
                node.prev = cur.prev
                cur.prev.next = node
                cur.prev = node
    
        def remove(self, item):
            """删除节点"""
            if self.is_empty():
                print("该链表为空，无法删除结点")
            else:
                cur = self.__head
    
                while cur != None:
    
                    if cur.elem == item:
    
                        if cur.prev != None:
                            cur.prev.next = cur.next
                        else:
                            self.__head = cur.next
    
                        if cur.next != None:
                            cur.next.prev = cur.prev
                        break
    
                    cur = cur.next
    
        def search(self, item):
            """查找节点是否存在"""
            cur = self.__head
            while cur != None:
                if cur.elem == item:
                    return "该结点存在"
                cur = cur.next
            return "该结点不存在"

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70]: /images/20210511/c1a81e20e8a549d6b9532da9921a8156.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDkxMjE1OQ_size_16_color_FFFFFF_t_70 1]: /images/20210511/35bf521bf05c44b08c1db86e98ca7544.png
[20200604103017603.png]: /images/20210511/6cb74e865c51456d805724e43633b414.png
[2020060410302724.png]: /images/20210511/81ee6fff236d4296841cd947eed4acd1.png
[2020060410303764.png]: /images/20210511/805eec188cdb42859ab809ac1dba0911.png
[2020060410304850.png]: /images/20210511/f95dc367bfa8482bb144c0233c79dfb6.png
[20200604103108751.png]: /images/20210511/6f4cc36006f74af19b5da0895f2c4e63.png