python中链式存储有哪些

Python013

python中链式存储有哪些,第1张

顺序存储结构最大的缺点是插入和删除时需要移动大量元素，耗费大量时间。

如果让相邻元素间留有足够余地，也就是不考虑相邻位置了，那么，我们这里可以引入链式存储结构。

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

二、链表的定义

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

1、单向链表

单向链表也叫单链表，是链表中最简单的一种形式，一个信息域(元素域)和一个链接域组成一个节点。

这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

链表的每个结点中只包含一个链接域，所以叫做单链表。

表元素域elem用来存放具体的数据。

链接域next用来存放下一个节点的位置(python中的标识)

变量p指向链表的头节点(首节点)的位置，从p出发能找到表中的任意节点。

链表中第一个结点的长处位置叫做头指针

显著性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示)

通常会在单链表的第一个结点前附设一个结点，称为头结点。它的信息域可以不存储数据，也可以存储线性表长度等附加信息，头结点的链接域指向第一个结点的指针。

头指针与头结点的异同

无论链表是否为空，头指针均不为空，头指针是链表的必要元素；头结点不一定是链表的必要要素。

头指针具有标识作用，所以常用头指针冠以链表的名字。

链表： 其中的各对象按线性顺序排列，其顺序有各个对象里的指针决定，为动态集合提供了一种简单而灵活的表示方法。

双向链表： 每一个元素都是一个对象，每个对象有一个关键字key和两个指针：next和prev。如果元素x没有前驱，所以是链表的第一个元素head,若元素x没有后继，因此是链表的最后一个元素tail。如果L.hand=NIL,则链表为空。