[数据结构与算法] 链接表总结

上一次说到了顺序表,链接表和顺序表一样,也是线性表。那为什么有了线性表还要有链接表呢?总之就是当数据过大时,顺序表存在一些存储方面的限制,而链接表比顺序表要更有效。链接表的主要不同之处在于使用了链接技术,那什么是链接技术?请看下面这个图

这个图是最简单的链接表,叫做单向链表,每一个位置上都存储着该位置的节点信息以及下一个位置的地址。就好像通过地址把顺序表的前一元素和后一元素链接起来了,所以叫链接技术。顺序表中前后元素也有关系,链接表和顺序表的区别是显式的而非隐式把这种关系表达出来。

这样做的好处是把表中元素都独立的存储在存储块中,这个存储块也叫表的节点。还有这样可以从表的任一个节点都可以找到与其关联的下一个节点。

下面开始具体说下单向链接表,也叫单链表或者链表

上面那个图就是一个单链表,单链表的结点是一个二元组,存储着值和下一个结点的标识,分别叫做值域和指针域,也叫元素域和链接域。单链表的结点之间通过结点链接建立起单向的顺序联系。单链表的结尾结点的链接域用空值来表示,在Python中就是None,有的语言里用0来表示。

下面我们开始说链接表的基本操作

创建空链表:要确定一个单链表,只要知道首结点就行,知道了首结点,就知道了下一个结点的元素,依次类推。所以创建一个空链表,既然为空,那就一个元素也没有,所以它的首元素的链接域也是一个空链接。

删除链表:要删除一个链表需要把链表中的元素全部删除,在Python中,只需要将表指针赋值为None,Python解释器的存储管理系统会自动回收不用的存储。

判断表是否为空:将表头变量的值与空链接比较,因为一个空链表的表头变量的值为空None,所以通过与空链接比较,就可以判断是否为空表。

判断表是否为满:顺序表在定义的时候,就会给定元素的最大存储数目,所以判断满很简单,就看元素个数是否等于最大存储数目。而链接不一样,一般来说,不存在满的链接表,除非数据占满了整个存储空间。

添加元素:给链表加入元素同样具有插入位置的问题,但是在链接表里面插入元素不需要对元素进行移动。因为插入新元素的操作是通过修改链接,接入到新的结点,从而改变了原来的表结构来实现的。

然后我们分别看一下,在表首端插入,在指定位置插入是怎么实现的。

表首端插入:插入新元素称为表的第一个元素。分三步来做,首先创建一个新结点并存入数据。注意这里只是创建了结点,和原链表并没有关系。然后把原链表首结点的链接存入刚才创建的结点的链接域。最后修改表头变量,使得表头变量指向新结点。简单用代码来表示一下这个过程就是:

q=LNode()
q.next = head.next
head=q

一般情况的元素插入:要想在单链接表里某位置插入一个新结点,必须找到该位置之前的那个结点,因为新结点需要插入在它的后面。需要修改它的链接域。我们也分三步来完成这个操作,首先创建一个新结点并存入数据。然后把前一元素的链接域指向新结点的链接域,最后修改前一元素的链接域,使之指向新结点。用代码来表示就是:

q=LNode()
q.next = pre.next
pre.next=q

删除元素: 删除元素和增加元素的原理是类似的,如果是删除首结点,只需要修改表头指针,令其指向第二个结点。丢弃不用的结点将被Python自动回收。删除其他位置的元素,需要修改上一个元素的链接域,使其指向下一个结点。这样中间这个元素就被删除了。

下面是一个链表的Python实现,首先定义结点类,然后定义链表类,以及各种操作的实现。

# - * - coding:utf-8 - * -
class LNode:
    def __init__(self, x, next_=None):
        self.elem=x
        self.next=next_
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 ValueError("in pop")
        e = self._head.elem
        self._head=self._head.next
        print("head is :%s"%self._head)
        return e
    # 后端操作
    def append(self,elem):
        if self._head is None:
            self._head = LNode(elem)
            return
        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 ValueError("in pop_last")
        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):
        p=self._head
        while p is not None:
            if pred(p.elem):
                return p.elem
            p=p.next
    def printall(self):
        p=self._head
        while p is not None:
             if p.next is not None:
                print(', ')
             p=p.next
if __name__=="__main__":
    node = LNode(elem=1, next_=2)
    print(node)
    mlist1 = LList()
    for i in range(5):
        mlist1.prepend(i)
    print(mlist1.is_empty())
    for i in range(15, 20):
        mlist1.append(i)
    mlist1.pop()
    mlist1.printall()

链表先到这里吧,看得我头疼,这点东西,搞了好几天。下次举几个链表的题目,通过例题理解的能深入一点。

原文发布于微信公众号 - 机器学习和数学(ML_And_Maths)

原文发表时间:2017-09-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

java中HashMap详解

通过HashMap、HashSet 的源代码分析其 Hash 存储机制 实际上,HashSet 和 HashMap 之间有很多相似之处,对于 HashSet ...

1632
来自专栏python3

Python变量类型

有符号整数,就是C语言中所指的整型,也就是数学中的整数,它的大小与安装的解释器的位数有关

1412
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

1933
来自专栏Python爬虫实战

LeetCode刷题:Array系列之Remove Element

#include <iostream> #include <vector> using namespace std;

811
来自专栏开发与安全

数据结构:双向链表实现队列与循环链表

一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,...

2478
来自专栏编程理解

数据结构(五):哈夫曼树(Huffman Tree)

哈夫曼树(或者赫夫曼树、霍夫曼树),指的是一种满二叉树,该类型二叉树具有一项特性,即树的带权路径长最小,所以也称之为最优二叉树。

2502
来自专栏你不就像风一样

Java核心数据结构(List,Map,Set)使用技巧与优化

JDK提供了一组主要的数据结构实现,如List、Map、Set等常用数据结构。这些数据都继承自 java.util.Collection 接口,并位于 java...

3483
来自专栏闪电gogogo的专栏

【数据结构(C语言版)系列一】 线性表

数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

6353
来自专栏黑泽君的专栏

异常中要了解的Throwable类中的几个方法

*   public String getMessage()   获取异常的信息,返回的是字符串

6791
来自专栏nnngu

010 有顺序的Map的实现类:TreeMap和LinkedHashMap

Map主要用于存储健值对,根据键得到值,因此不允许键重复,但允许值重复。 HashMap   说到Map,首先能想起的是HashMap,它是一个最常用的Map,...

3605

扫码关注云+社区

领取腾讯云代金券