链表

作者: 心_7e09 | 来源:发表于2019-04-09 17:34 被阅读0次

Python的list类是高度优化的,并且通常是考虑存储问题时很好的选择。除此之外,list类也有一些明显的缺点。
1)一个动态数组的长度可能超过实际存储数组元素所需的长度。
2)在实时系统中对操作的摊销边界是不可接受的。
3“)在一个数组内部执行插入和删除操作的代价太高。
在本篇文章,我们介绍一个名为链表的数据结构,它为基于数组的序列提供了另一种选择。一个链表依赖于更多的分布式表示法,采用称作节点的轻量级对象,分配给每一个元素。每个节点维护一个指向它的元素的引用,并含一个或多个指向相邻节点的引用,这样做的目的是为了集中地表示序列的线性顺序。

单向链表

单向链表最简单的实现形式就是由多个系欸单的集合共同构成一个线性序列,每个节点存储一个对象的引用。
每个节点被表示为唯一的对象,该对象实例存储着指向其元素成员的引用和指向下一个节点的引用。另一个对象用于代表整个链表。链表实例至少必须包括一个指向链表头节点地引用。

# 用单向链表实现栈
from queue import Empty


class LinkedStack:
    class _Node:
        __slots__ = '_element', '_next'

        def __init__(self, element, next):
            self._element = element
            self._next = next
            
    def __init__(self):
        self._head = None
        self._size = 0
        
        
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0
    
    def push(self,e):
        self._head = self._Node(e,self._head)
        self.size += 1
        
    def top(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        
        return self._head._element
    
    def pop(self):
        if self.is_empty():
            raise Empty('Stack is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        return answer
# 用单向链表实现队列

class LinkedQueue:
   class _Node:
       __slots__ = '_element', '_next'

       def __init__(self, element, next):
           self._element = element
           self._next = next
   
   def __init__(self):
       self._head = None
       self._tail = None
       self.__size = 0
       
   def __len__(self):
       return self.__size
   
   def is_empty(self):
       return self.__size == 0
   
   def first(self):
       if self.is_empty():
           raise Empty('Stack is empty')
       
       return self._head._element
   
   def dequeue(self):
       if self.is_empty():
           raise Empty('Stack is empty')
       answer = self._head._element
       self._head = self._head._next
       self._size -= 1
       if self.is_empty():
           self._tail = None
       return answer
   
   def enqueue(self,e):
       newest = self._Node(e,None)
       if self.is_empty():
           self._head = newest
       else:
           self._tail._next = newest
       self._tail = newest
       self._size += 1
   ```
### 循环链表
在链表中,我们可以使链表的尾部节点地"next"指针指向链表的头部,由此来获得一个更切实际的循环链表的概念,我们称这种表结构为循环链表。
### 双向链表
在使用哨兵时,实现方法的关键是要记住双端队列的第一个元素并不存储在头节点,而是存储在头节点后的第一个节点,同样,尾节点之前的一个节点中存储的是双端队列的最后一个元素。
### 位置列表的抽象数据类型
我们希望能够设计一个抽象数据类型为用户提供一种可以定位到序列中任何元素的方法,并且能够执行任意的插入和删除操作。
链表结构的好处之一是:只要给出列表相关节点的引用,它可以实现在列表的任意位置执行插入和删除操作的时间复杂度都是O(1)。
为了给具有标识元素位置能力的元素序列提供一般化抽象,我们定义了一个含位置信息的列表ADT以及一个更简单的位置抽象数据类型,来描述列表中的某个位置。




















相关文章

  • 链表基础

    链表基础 链表长度 链表为空 链表结构 链表增加

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

  • 算法与数据结构:链表

    链表 链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...

  • 链表

    链表 单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数 一.单向链表 链表共有特征...

  • 五、双向链表

    双向链表 此前介绍的链表,也叫做单向链表使用双向链表可以提升链表的综合性能 修改之前的单链表的源码: 双向链表 –...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • 数据与算法结构

    线性表 顺序表 链表(物理上离散,逻辑上连续) 链表的类别 单链表 循环链表 双链表 链表的操作 顺序表与链表的比...

  • 数据结构——链表

    本文所讲的链表是单链表,链表采用无头链表 科普下:一般链表可以分为有头节点的链表与无头节点的链表 有头节点的链表:...

  • 链表

    文章结构 链表的定义 链表的插入和删除操作 链表的特性 常见的链表结构 自定义链表 链表的经典操作 使用链表实现L...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下: 1.1 递归反转整个单链表...

网友评论

      本文标题:链表

      本文链接:https://www.haomeiwen.com/subject/wuibiqtx.html