线性表的原理与实现
2019-11-10 本文已影响0人
愤怒的谜团
一、线性表的顺序存储结构
1.线性表（List）的定义
由零个或多个数据元素组成的有限序列，数据元素类型可以是基本类型，也可以是抽象类型class，把它想象成一个结点就行。
2. 线性表的顺序存储
顺序存储是由在内存当中一块连续的空间组成的，这块内存空间，在创建线性表时就需要确定大小，这一点刚好对应了java当中的数组，java创建一个数组，会返回一个引用，数组元素存于堆内存当中，是一块连续的空间，引用是存于栈当中，使用时push进栈。
顺序存储.png
3. 顺序存储的优势
存取速率快，时间复杂度为O(1)，因为数据元素存于地址连续的内存空间当中，每一个小结点，分配的大小是固定的，比如int分配8字节，那么很快可以根据存取的脚标计算出结点的位置。并且顺序存储不需要开辟空间去存储下一个结点的引用，节省了内存开销。
4.顺序存储的劣势
增删结点会有较多不便，想象一下，最好的情况是在线性表的最后一个结点进行增删，那么时间复杂度是O(1)，因为其他数据元素不需要进行位移。最糟糕的情况，在线性表的第一个结点进行增删，那么时间复杂度是O(n)，n被称作问题规模，简单理解为数据量，平均一下，时间复杂度也有(n+1)/2。
二、线性表的链式存储结构
1. 线性表的链式存储
这种方式底层不在是采用数组的方式，因为在链式存储方式下，相邻的两个数据元素存储的位置不在连续的内存空间，那如何体现线性表的有序呢？每个数据元素除了存储元素值以外，还需要额外开辟空间来存储指向下个数据元素的引用，这样就可以将不同结点链接起来。
链式存储.png
2.链式存储的优势
之前用顺序存储的模式，在进行增删的时候，只要不是最后一个结点，就会产生大量数据元素的位移，用链式存储可以很好的解决这个问题，因为链式存储只要修改一下引用的指向就可以了，不需要位移任何元素，时间复杂度为O(1)，但是这里有一点，就是遍历查找需要增删数据元素的复杂度，也为O(n)，但是对于批量增删来说，链式存储还是有很明显的优势的。并且链式存储不需要一开始就固定线性表的大小，即用即申请，非常方便。
3.链式存储的劣势
链式存储需要为每一个结点单独开辟一个内存空间来存储引用。并且由于每个数据元素存储的内存位置不是连续的，存取时遍历带来的时间复杂度为O(n)。
三、顺序存储的实现-java
import java.util.ArrayList;
public class MyArrayList {
/**
* 线性表反应的是若干数据元素之间的线性关系，与树不同，元素之间的关系都是一对一的
* 线性表存在两种存储方式：顺序存储，链式存储
*/
/**
* 线性表一般具有以下功能：
* 1.InitList(int Maxlenth) 初始化操作，建立一个空的线性表
* 2.ListEmpty() 判断线性表是否为空，为空则返回true，非空返回false
* 3.ClearList() 将线性表清空
* 4.GetElem(int index) 返回位置index的元素
* 5.LocateElem(T elem) 返回与给定elem值相等的元素，返回第一个相同值的脚标
* 6.ListInsert(T elem) 在线性表末尾插入数据，不需要手动指定位置
* 7.ListInsertWithIndex(int index,T elem) 在线性表脚标为index处插入新元素
* 8.ListDelete(int index) 删除线性表脚标为index的元素，并返回其值
* 9.ListLenth() 返回当前线性表的长度
* 10.toString() 打印当前线性表的所有元素值，用逗号分隔
*/
/**
* 使用顺序存储的方式来实现一个线性表，即java数组。
*/
int MaxLenth; //定义该线性表最大存储空间
int Currlength = 0; //定义该线性表当前大小
int[] myArrayList = null;
//实现InitList功能
public MyArrayList(int Maxlenth){
// 以整型数组为例
myArrayList = new int[Maxlenth];
this.MaxLenth = Maxlenth;
}
//实现ListEmpty功能
public Boolean ListEmpty(){
return Currlength == 0?true:false;
}
//实现ClearList功能
public int[] ClearList(){
/**
* java当中没有手动操作内存的API，不想C语言当中的指针，但是当一块内存没有引用
* 指向时，就会开始等待GC（JVM的垃圾回收机制）
*/
return new int[MaxLenth];
}
//实现GetElem的功能
public int GetElem(int index){
if (index < 0 || index >= Currlength){return -1;}
else {return myArrayList[index];}
}
//实现LocateElem(T elem)功能
public int LocateElem(int elem){
for (int head = 0;head < Currlength;head++){
if (myArrayList[head] == elem){return head;}
else {continue;}
}
return -1;//返回-1表示未找到有与其对应的元素值
}
//实现ListInsert(int index,T elem)功能
public Boolean ListInsert(int elem){
if (Currlength == MaxLenth){return false;}
myArrayList[Currlength++] = elem;
return true;
}
//ListInsertWithIndex(int index,T elem)功能
public Boolean ListInsertWithIndex(int index,int elem){
/**
* 插入操作会相对复杂一些，由于数组这种顺序结构，插入会导致
* 被插元素后面的所有元素需要后移一位
*/
if (Currlength == MaxLenth){return false;}
if (Currlength == 0){myArrayList[0] = elem; Currlength++;return true;}
for (int rear = Currlength;rear >= index;rear--){
myArrayList[rear] = myArrayList[rear-1];
}
myArrayList[index] = elem;
Currlength++;
return true;
}
//实现ListDelete(int index)功能
public int ListDelete(int index){
/**
* 与插入操作相反，删除操作需要将被删元素后面所有元素都向前移一位
*/
if (Currlength == 0 ){return -1;}
int returnTempElem = -1;
for (int start = index;index < Currlength;index++){
returnTempElem = myArrayList[index];
myArrayList[index] = myArrayList[index+1];
}
Currlength--;
return returnTempElem;
}
//实现ListLenth()的功能
public int ListLenth(){
return Currlength;
}
//实现toString方法
public String toString(){
StringBuffer returnTempString = new StringBuffer();
for (int start = 0;start<Currlength;start++){
if (start != Currlength-1){
returnTempString.append(myArrayList[start] + ",");
}else {
returnTempString.append(myArrayList[start]);
}
}
return returnTempString.toString();
}
public static void main(String[] args) {
}
}
四、链式存储的实现-java
public class MyLinkedList {
/**
* 线性表反应的是若干数据元素之间的线性关系，与树不同，元素之间的关系都是一对一的
* 线性表存在两种存储方式：顺序存储，链式存储
*/
/**
* 线性表一般具有以下功能：
* 1.InitList() 初始化操作，建立一个空的线性表
* 2.LinkedListEmpty() 判断线性表是否为空，为空则返回true，非空返回false
* 3.ClearLinkedList() 将线性表清空
* 4.GetLinkedElem(int index) 返回位置index的元素
* 5.LocateLinkedElem(T elem) 返回与给定elem值相等的元素，返回第一个相同值的脚标
* 6.LinkedListInsert(T elem) 在线性表末尾插入数据，不需要手动指定位置
* 7.LinkedListInsertWithIndex(int index,T elem) 在线性表脚标为index处插入新元素
* 8.LinkedListDelete(int index) 删除线性表脚标为index的元素，并返回其值
* 9.LinkedListLenth() 返回当前线性表的长度
* 10.toString() 打印当前线性表的所有元素值，用逗号分隔
*/
/**
* 使用链式存储的方式来实现一个线性表
*/
private int CurrLenth = 0; //线性表的大小
private LinkedNode headNode = null; // 头结点
private LinkedNode rear = null; //尾指针，方便线性表尾部的操作
class LinkedNode{
String nodeData; //存储节点数据
LinkedNode next; //存储指向下一个节点的位置
}
public MyLinkedList(){
/**
* 初始化一个链式存储的线性表，生成头结点，尾指针
*/
this.headNode = new LinkedNode();
headNode.nodeData = null; //头结点的数据域不需要存储数据
headNode.next = null; //初始化一个链式存储的线性表，由于没有第一个结点，所以头结点的next为空
this.rear = headNode; //将尾部指针指向头结点
}
//实现LinkedListEmpty的功能
public Boolean LinkedListEmpty(){
//头结点默认不算长度
return CurrLenth == 0?true:false;
}
//实现ClearLinkedList的功能
public Boolean ClearLinkedList(){
/**
* 由于java不能手动释放内存占用，只能依靠GC机制，所以这边需要循环
* 将每个指向结点的引用置为空，这样当一块内存没有引用指向时，JVM
* 会自动回收。
*/
if (CurrLenth == 0){return true;} //空链表，直接返回true
LinkedNode index = headNode.next; //该游标作用是保存释放结点前,存放该结点的指针域数据
LinkedNode currIndex = headNode.next; //该游标作用是指向待释放结点对象
// headNode.next = null; //释放头结点对一个结点的链接
if (CurrLenth == 1){
//表示只有一个结点时
index = null;
currIndex = null;
headNode.next = null;
// 释放完以后的初始化操作
CurrLenth = 0;
rear = headNode;
return true;
}
for (;index.next != null;){
index = currIndex.next;
currIndex.next = null;
currIndex = index;
}
// 释放临时游标指针
index = null;
currIndex = null;
// 释放头结点链接
headNode.next = null;
// 释放完以后的初始化操作
CurrLenth = 0;
rear = headNode;
return true;
}
//实现GetLinkedElem的功能
public String GetLinkedElem(int index){
if (index <= 0 || index > CurrLenth){return "error";}
// 假设头结点为index=0，第一个结点index=1
LinkedNode currIndex = headNode.next;
for (int curr = 1;curr <= index;curr++,currIndex = currIndex.next){
if (curr == index){
return currIndex.nodeData;
}else{
continue;
}
}
return "error";
}
//实现LocateLinkedElem的功能
public int LocateLinkedElem(String elem){
if (CurrLenth == 0){return -1;}
LinkedNode start = headNode.next;
int index = 1;
for(;start != null;start = start.next,index++){
if (start.nodeData.equals(elem)){return index;}
else{
continue;
}
}
return -1;
}
//实现LinkedListInsert的功能
public Boolean LinkedListInsert(String elem){
/**
* 要插入一个新的结点，需要考虑什么，跟顺序存储不同，链式存储可以称得上有
* 无限空间，除非堆内存溢出了，所以不需要判断是否空间不足
*/
try{
LinkedNode linkedNode = new LinkedNode();
linkedNode.nodeData = elem;
if (headNode.next == null){
// 头结点为空，表示插入的是第一个结点
headNode.next = linkedNode;
rear = linkedNode;
CurrLenth++;
return true;
}else{
rear.next = linkedNode; //让尾指针指向下一个结点，即将该结点放于线性表最后的位置
linkedNode.next = null;
rear = rear.next;
CurrLenth++;
return true;
}
}catch(Exception e){
System.out.println("Add LinkedNode Find unknow Error!"+e);
return false;
}
}
//实现LinkedListInsertWithIndex功能
public Boolean LinkedListInsertWithIndex(int index,String elem){
if (index <= 0 || index > CurrLenth+1){
// 当index = CurrLenth+1时，表示需要插入到链表尾部
return false;
}
int currIndex = 1; //当前脚标
LinkedNode currNode = headNode.next;
LinkedNode insertNode = null; //待插入的结点
if (index == 1){
// 表示要插入到头结点后面的第一个结点，需要修改头结点
insertNode = new LinkedNode();
insertNode.nodeData = elem;
insertNode.next = currNode;
headNode.next = insertNode;
CurrLenth++;
return true;
}
if (index == CurrLenth+1){
//表示是插入最后结点后面的位置，这种情况需要修改尾指针
insertNode = new LinkedNode();
rear.next = insertNode;
insertNode.nodeData = elem;
insertNode.next = null;
rear = insertNode;
CurrLenth++;
return true;
}
while (currIndex != index-1){
// 主要是遍历出要插入的前一个结点所处的位置
currIndex++;
currNode = currNode.next;
}
LinkedNode nextNode = currNode.next;
insertNode = new LinkedNode();
insertNode.nodeData = elem;
currNode.next = insertNode;
insertNode.next = nextNode;
CurrLenth++;
return true;
}
//实现LinkedListDelete功能
public String LinkedListDelete(int index){
if (index <=0 || index > CurrLenth){return "error";}
int currIndex = 1;
LinkedNode currNode = headNode.next;
LinkedNode realseNode = null; //待释放的结点
String returnString = null; //待返回的字符串
if (index == 1){
// 表示要删除头结点后面的位置，操作特殊，需要修改头结点指针域
if (headNode.next.next != null){
// 说明链表不止一个结点，删除第一个结点，不需要修改尾指针
returnString = currNode.nodeData;
realseNode = currNode;
headNode.next = currNode.next;
realseNode.next = null;
CurrLenth--;
return returnString;
}else {
returnString = currNode.nodeData;
currNode.next = null;
headNode.next = null;
rear = headNode;
CurrLenth--;
return returnString;
}
}
while (currIndex != index-1){
currIndex++;
currNode = currNode.next;
}
if (currIndex+1 == CurrLenth){
// 表示删除的是最后一个结点，所以需要修改尾指针
rear = currNode; // 首先将尾指针指向即将删除的尾结点的前一个结点
realseNode = currNode.next;
returnString = realseNode.nodeData;
currNode.next = null;
realseNode.next = null;
CurrLenth--;
return returnString;
}else{
realseNode = currNode.next;
returnString = realseNode.nodeData;
currNode.next = realseNode.next;
realseNode.next = null;
CurrLenth--;
return returnString;
}
}
//实现LinkedListLenth的功能
public int LinkedListLenth(){
return CurrLenth;
}
//实现toString的功能
public String toString(){
StringBuffer stringBuffer = new StringBuffer();
if (headNode.next == null){return "";} //表示是空链表
if (headNode.next != null && headNode.next.next == null){
// 表示该线性表只存在一个结点
return headNode.next.nodeData;
}
for (LinkedNode start = headNode.next;start != null;start = start.next){
if (start.next == null){
//表示是最后一个结点
stringBuffer.append(start.nodeData);
}else{
stringBuffer.append(start.nodeData+",");
}
}
return stringBuffer.toString();
}
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.LinkedListInsert("Hello");
myLinkedList.LinkedListInsert("world");
myLinkedList.LinkedListDelete(1);
System.out.println(myLinkedList.toString());
// System.out.println(myLinkedList.toString()); // Hello,world
// System.out.println(myLinkedList.LinkedListEmpty()); //false
// System.out.println(myLinkedList.LinkedListLenth()); // 2
// myLinkedList.ClearLinkedList();
// System.out.println(myLinkedList.toString()); // 为空
// System.out.println(myLinkedList.GetLinkedElem(1)); // hello
// System.out.println(myLinkedList.GetLinkedElem(2)); // world
// System.out.println(myLinkedList.GetLinkedElem(3)); // error
// System.out.println(myLinkedList.GetLinkedElem(-1)); // error
// System.out.println(myLinkedList.LocateLinkedElem("Hello")); // 1
// System.out.println(myLinkedList.LocateLinkedElem("world")); // 2
// System.out.println(myLinkedList.LocateLinkedElem("world1")); // -1
// myLinkedList.LinkedListInsertWithIndex(2,"insert");
// System.out.println(myLinkedList.toString()); // Hello,insert,world
//
// myLinkedList.LinkedListInsertWithIndex(1,"start");
// System.out.println(myLinkedList.toString()); // start,Hello,insert,world
//
// myLinkedList.LinkedListInsertWithIndex(5,"end");
// System.out.println(myLinkedList.toString()); // start,Hello,insert,world,end
//
// myLinkedList.LinkedListInsertWithIndex(7,"error");
// System.out.println(myLinkedList.toString()); // start,Hello,insert,world,end
// myLinkedList.LinkedListDelete(1);
// System.out.println(myLinkedList.toString()); // Hello
//
// myLinkedList.LinkedListDelete(0);
// System.out.println(myLinkedList.toString()); // Hello
}
}
五、两种存储方式时间复杂度分析
| 最好情况时间复杂度 | 最差情况时间复杂度 | 平均时间复杂度 | |
|---|---|---|---|
| 顺序存储的存取 | O(1) | O(1) | O(1) |
| 顺序存储的增删 | O(1) | O(n) | O((n+1)/2)=O(n) |
| 链式存储的存取 | O(1) | O(n) | O((n+1)/2)=O(n) |
| 链式存储的增删(去除遍历的开销) | O(1) | O(1) | O(1) |
所以综合来讲，顺序存储的方式适合多存取，少增删，并且能够确定线性表大小的场景。链式存储适合多增删，少存取，无法确定线性表大小的场景。
代码进行过简单的校验，如果存在bug，望私信指正！
