数据结构于算法—线性表详解(顺序表、链表)

• 2019 年 10 月 6 日
• 筆記

前言

• 通过前面数据结构与算法前导我么知道了数据结构的一些概念和重要性，那么我们今天总结下线性表相关的内容。当然，我用自己的理解解分享给大家。
• 其实说实话，可能很多人依然分不清线性表，顺序表，和链表之间的区别和联系！
  • 线性表：逻辑结构， 就是对外暴露数据之间的关系，不关心底层如何实现。
  • 顺序表、链表：物理结构，他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
• 对于java来说，大家都知道List接口类型，这就是逻辑结构，因为他就是封装了一个线性关系的一系列方法和数据。而具体的实现其实就是跟物理结构相关的内容。比如顺序表的内容存储使用数组的，然后一个get，set，add方法都要基于数组来完成,而链表是基于指针的。当我们考虑对象中的数据关系就要考虑指针的属性。指针的指向和value。

下面用一个图来浅析线性表的关系。可能有些不太确切，但是其中可以参考，并且后面也会根据这个图举例。

线性表基本架构

• 对于一个线性表来说。不管它的具体实现方法如何，我们应该有的函数名称和实现效果应该一致。你也可以感觉的到在一些结构的设计。比如List的Arraylist和LinkedList。Map的HashMap和currentHashMap他们的接口api都是相同的，但是底层设计实现肯定是有区别的。
• 所以，基于面向对象的编程思维，我们可以将线性表写成一个接口，而具体实现的顺序表和链表可以继承这个接口的方法，提高程序的可读性。
• 还有一点比较重要的，记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着知识的进步，我们应当采用泛型来实现更合理。至于接口的具体设计如下：

package LinerList;  public interface ListInterface<T> {  	void Init(int initsize);//初始化表  	int length();  	boolean isEmpty();//是否为空  	int ElemIndex(T t);//找到编号  	T getElem(int index) throws Exception;//根据index获取数据  	void add(int index,T t) throws Exception;//根据index插入数据  	void delete(int index) throws Exception;  	void add(T t) throws Exception;//尾部插入  	void set(int index,T t) throws Exception;  	String toString();//转成String输出  }  

顺序表

• 顺序表是基于数组实现的，所以一些方法要基于数组的特性。对于顺序表应该有的基础属性为一个数组data和一个length.
• 还有需要注意的是初始化数组的大小，你可以固定大小，但是笔者为了可用性如果内存不够将扩大二倍。当然这样很可能因为空间使用问题造成很大的浪费。
• 一些基本的额方法就不说了，下面着重讲解一些初学者容易混淆的概念和方法实现。这里把顺序表比作一队坐在板凳上的人。

插入

add(int index,T t)

• 其中index为插入的编号位置，t为插入的数据

• 根据图片你就很好理解插入操作。当插入一个index时候，他的后面所有元素都要后移一位。你可以看的出插入时候整个操作的臃肿性。所以这也是顺序表性能表现最差的地方,频繁的插入，删除。

删除

• 同理，删除也是非常占用资源的。原理和插入类似，不过人走了，空一个小板凳后面的人需要往前挪。

其他操作

• 其他操作就很简单了。比如如果按照编号获取数据getElem(int index)，你可以直接根据数据坐标返回。a[index]，而其他操作，可以通过遍历直接操作数组即可。

链表

• 我想，表应该是很多人感觉很绕的东西，这个很大原因可能因为指针。很多人说java没指针，其实java他也有隐形指针。只不过不能直接用罢了。
• 指针建立的数据关系往往比数组这些要抽象的多。对于指针域，你把他当成一个对象就好了，不过这个对象指向的是另一个同等级对象。对于这个关系，你可以比作每个person类。每个person类都有老公(老婆),而这个老公老婆也是一个实际对象，可以理解这更像一种逻辑约定关系，而不是硬生生的关系吧。

• 指针你可以考虑成脑子记忆。上面的顺序表我们说它有序因为每个小板凳(数组)有编号，我们可以根据这个来确定位置。而对于链表来说，你可以看作成一个站在操场上的一队人。而他的操作也略有不同，下面针对一些比较特殊和重要的进行归纳。

基本结构

对于线性表，我们只需要一个data数组和length就能表示基本信息。而对于链表，我们需要一个node(head头节点)，和length,当然，这个node也是一个结构体。

class node<T>{      T data;//节点的结果      node next;//下一个连接的节点      public node(){}      public node(T data)      {          this.data=data;      }      public node(T data, node next) {          this.data = data;          this.next = next;      }  }  

当然，这个节点有数据域和指针域。数据域就是存放真实的数据，而指针域就是存放下一个node的指针。所以相比顺序表，如果用满数组情况下，链表占用更多的资源，因为它要存放指针占用资源。

插入

add(int index,T t) 其中index为插入的编号位置，t为插入的数据 加入插入一个节点node，根据index找到插入的前一个节点叫pre。那么操作流程为

1. node.next=pre.next如下1的操作，将插入节点后面联系起来。此时node.next和pre.next一致。
2. pre.next=node因为我们要插入node，而node链可以替代pre自身的next。那么直接将pre指向node。那么就相当于原始链表插入了一个node。

带头节点与不带头节点

很多人搞不清什么是带头节点和不带头节点。带头节点就是head节点不放数据，第0项从head后面那个开始数。而不带头节点的链表head放数据，head节点就是第0位。 主要区别：

• 带头节点和不带头节点的主要区别就在插入删除首位，尤其是首位插入。带头节点找元素需要多遍历一次因为它的第一个head节点是头节点，不存数据(可看作一列火车的火车头)。而方便的就是带头节点在首位插入更简单。因为插入第0位也是在head的后面。
• 而不带头节点的链表就需要特殊考虑首位。因为插入第0位其实是插入head的前面。假设有head，插入node。具体操作为：

1. node.next=head；(node指向head，node这条链成我们想要的链)
2. head=node；(很多人想不明白，其实这个时候node才是插入后最长链的首位节点，head在他的后面，而在链表中head通常表示首位节点，所以head不表示第二个节点，直接"="node节点。这样head和node都表示操作完成的链表。但是对外暴露的只有head。所以head只能指向第一个节点！)

插入尾

• 而在插入尾部的时候，需要注意尾部的next为null。不能和插入普通位置相比！

删除

按照index移除：delete(int index)

• 找到该index的节点node。node.next=node.next.nex

按照尾部移除(拓展)：deleteEnd()

• 这个方法我没有写，但是我给大家讲一下，按照尾部删除的思想就是：
  1. 声明一个node为head。
  2. 当node.next！=null时node=node.next 指向下一个
  3. 当node.next==null时候。说明这个节点时最后一个。你可以node=null。这个这个node的前驱pre的next就是null。这个节点就被删除了。

头部删除(带头节点)：

• 带头节点的删除和普通删除一直。直接head.next(第1个元素)=head.next.next(第二个元素)
• 这样head.next就直接指向第二个元素了。第一个就被删除了

头部删除(不带头节点)

• 我们知道不带头节点的第一个就是存货真价实的元素的。不带头节点删除也很简单。直接将head移到第二位就行了。即：head=head.next

其他

• 对于其他操作，主要时结合查找。而单链表的查找时从head开始。然后另一个节点team=head或head.next。然后用这个节点不停的等于它指向的next去查找我们需要的内容即while(循环条件){team=team.next}类似。
• 不同教程和人写的线性表也不一致，这里只给出一个样例学习使用而并不是标准，希望大家审视。
• 在实现上用了带头节点的链表实现，因为比较方便管理，不需要很多if else.

代码实现

顺序表

package LinerList;    public class seqlist<T> implements ListInterface<T> {  	private Object[] date;//数组存放数据  	private int lenth;  	public seqlist() {//初始大小默认为10  		Init(10);  	}    	public void Init(int initsize) {//初始化  		this.date=new Object[initsize];  		lenth=0;  	}  	public int length() {  		return this.lenth;  	}    	public boolean isEmpty() {//是否为空  		if(this.lenth==0)  			return true;  		return false;  	}    	/*  	 * * @param t  	 * 返回相等结果，为-1为false  	 */  	public int ElemIndex(T t) {  		// TODO Auto-generated method stub  		for(int i=0;i<date.length;i++)  		{  			if(date[i].equals(t))  			{  				return i;  			}  		}  		return -1;  	}    	/*  	 *获得第几个元素  	 */  	public T getElem(int index) throws Exception {  		// TODO Auto-generated method stub  		if(index<0||index>lenth-1)  			throw new Exception("数值越界");  		return (T) date[index];  	}    	public void add(T t) throws Exception {//尾部插入  		 add(lenth,t);  	}    	/*  	 *根据编号插入  	 */  	public void add(int index, T t) throws Exception {  		if(index<0||index>lenth)  			throw new Exception("数值越界");  		if (lenth==date.length)//扩容  		{  			Object newdate[]= new Object[lenth*2];  			for(int i=0;i<lenth;i++)  			{  				newdate[i]=date[i];  			}  			date=newdate;  		}  		for(int i=lenth-1;i>=index;i--)//后面元素后移动  		{  			date[i+1]=date[i];  		}  		date[index]=t;//插入元素  		lenth++;//顺序表长度+1    	}    	public void delete(int index) throws Exception {  		if(index<0||index>lenth-1)  			throw new Exception("数值越界");  		for(int i=index;i<lenth;i++)//index之后元素前移动  		{  			date[i]=date[i+1];  		}  		lenth--;//长度-1  	}    	@Override  	public void set(int index, T t) throws Exception {  		if(index<0||index>lenth-1)  			throw new Exception("数值越界");  		date[index]=t;  	}  	public String  toString() {  		String vaString="";  		for(int i=0;i<lenth;i++)  		{  			vaString+=date[i].toString()+" ";  		}  		return vaString;    	}  }    

链表

package LinerList;    class node<T>{      T data;//节点的结果      node next;//下一个连接的节点      public node(){}      public node(T data)      {          this.data=data;      }      public node(T data, node next) {          this.data = data;          this.next = next;      }    }  public class Linkedlist<T> implements ListInterface<T>{    	node head;  	private int length;  	public Linkedlist() {  		head=new node();  		length=0;  	}  	public void Init(int initsize) {  		head.next=null;    	}    	public int length() {          return this.length;  	}      	public boolean isEmpty() {  		if(length==0)return true;  		else return false;  	}    	/*  	 * 获取元素编号  	 */  	public int ElemIndex(T t) {  		node team=head.next;  		int index=0;  		while(team.next!=null)  		{  			if(team.data.equals(t))  			{  				return index;  			}  			index++;  			team=team.next;  		}  		return -1;//如果找不到  	}    	@Override  	public T getElem(int index) throws Exception {  		node team=head.next;  		if(index<0||index>length-1)  		{  			throw new Exception("数值越界");  		}  		for(int i=0;i<index;i++)  		{  			team=team.next;  		}  		return (T) team.data;  	}      	public void add(T t) throws Exception {  		add(length,t);    	}  	//带头节点的插入，第一个和最后一个一样操作  	public void add(int index, T value) throws Exception {  		if(index<0||index>length)  		{  			throw new Exception("数值越界");  		}  		node<T> team=head;//team 找到当前位置node  		for(int i=0;i<index;i++)  		{  		     team=team.next;  		}  		node<T>node =new node(value);//新建一个node  		node.next=team.next;//指向index前位置的下一个指针  		team.next=node;//自己变成index位置  		length++;  	}      	@Override  	public void delete(int index) throws Exception {  		if(index<0||index>length-1)  		{  			throw new Exception("数值越界");  		}  		node<T> team=head;//team 找到当前位置node  		for(int i=0;i<index;i++)//标记team 前一个节点  		{  		     team=team.next;  		}  		//team.next节点就是我们要删除的节点  		team.next=team.next.next;  		length--;  	}    	@Override  	public void set(int index, T t) throws Exception {  		// TODO Auto-generated method stub  		if(index<0||index>length-1)  		{  			throw new Exception("数值越界");  		}  		node<T> team=head;//team 找到当前位置node  		for(int i=0;i<index;i++)  		{  		     team=team.next;  		}  		team.data=t;//将数值赋值，其他不变    	}    	public String toString() {  		String va="";  		node team=head.next;  		while(team!=null)  		{  			va+=team.data+" ";  			team=team.next;  		}  		return va;  	}    }    

测试与结果

package LinerList;  public class test {  	public static void main(String[] args) throws Exception {  		// TODO Auto-generated method stub  		System.out.println("线性表测试：");  		ListInterface<Integer>list=new seqlist<Integer>();  		list.add(5);  		list.add(6);  		list.add(1,8);  		list.add(3,996);  		list.add(7);  		System.out.println(list.ElemIndex(8));  		System.out.println(list.toString());  		list.set(2, 222);  		System.out.println(list.toString());  		list.delete(4);  		System.out.println(list.toString());  		System.out.println(list.length());    		System.out.println("链表测试：");  		list=new Linkedlist<Integer>();  		list.add(5);  		list.add(6);  		list.add(1,8);  		list.add(3,996);  		list.add(7);  		System.out.println(list.ElemIndex(8));  		System.out.println(list.toString());  		list.set(2, 222);  		System.out.println(list.toString());  		list.delete(4);  		System.out.println(list.toString());  		System.out.println(list.length());  	}  }    

输出:

线性表测试： 1 5 8 6 996 7 5 8 222 996 7 5 8 222 996 4 链表测试： 1 5 8 6 996 7 5 222 6 996 7 5 222 6 996 4

总结

• 这里的只是简单实现，实现基本方法。链表也只是单链表。完善程度还可以优化。如果有错误还请大佬指正。
• 单链表查询速度较慢，因为他需要从头遍历。如果频繁操作尾部，可以考虑链表中不仅有head在加尾tail节点。而顺序表查询速度虽然快但是插入很费时费力。实际应用根据需求选择！
• java中的Arraylist和LinkedList就是两种方式的代表，不过LinkedList使用双向链表优化，并且jdk的api做了大量优化。所以大家不用造轮子，可以直接用，但是还是很有学习价值的。