• 博客主页(4条消息) 小吴_小吴有想法_CSDN博客-笔记,java,leetcode领域博主
• 欢迎关注点赞收藏和留言
• 天道酬勤，勤能补拙，和小吴一起加油吧 
• 17岁大一新生，水平有限，恳请各位大佬指点，不胜感激! 
• 参考书籍《算法4》，学习视频：黑马程序员Java数据结构与java算法，全网资料最全数据结构+算法教程，154张java数据结构图_哔哩哔哩_bilibili

目录

线性表 

顺序表

代码实现

时间复杂度 

链表

单向链表

 单向链表代码实现

 双向链表

 代码实现

时间复杂度分析

---

 

线性表 

 线性表是最简单，最基本，也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。(一排高矮不同的人)

前驱元素：若A在B的前面，则称A为B的前驱元素

后继元素：若B在A的后面，则称B为A的后驱元素 

 线性表的特征：

• 第一个数据元素没有前驱，这个数据元素称为"头结点"
• 最后一个数据元素没有后继,这个数据元素称为"尾结点"
• 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前缀和后缀

线性表用数学语言来定义，可表示为(a1,,,ai-1,ai,ai+1,,,an),ai-1是ai的前驱元素，ai+1是ai的后驱元素

线性表中数据的储存方式的不同可以将线性表分为顺序表和链表

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的储存单元，依次存储线性表中的各个元素，使得线性表中在逻辑结构中响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系 

11

32

65

14

32

22

14

8

12

                          0           1            2          3          4           5           6         7         8

像这种数组形式方便理解

顺序表的代码实现:

代码实现

public class SequenceList<T> {//存储元素的数组private T[] a;//记录顺序表中的元素个数private int N;//构造方法public 	SequenceList(int capacity){ //初始化数组this.a=(T[])new Object[capacity];this.N=0;}//将一个线性表置为空表public void reset() {this.N=0;}//判断当前线性表是否为空表public boolean isEmpty(){return N==0;}//获取线性表的长度public int length(){return N;}//获取指定位置的元素public T get(int i){return a[i];}//向线性表中添加元素public void insert(T t){a[N++]=t;}//在i元素处插入元素tpublic void insert(int i,T t){//先把i索引处的元素及其后面索引处的元素依次向后移动一位for(int index=N-1;index>i;index--){a[index]=a[index-1];}//再把t元素放到i元素处即可a[i]=t;}//删除指定位置i处的元素，并返回该元素public T remove(int i){//记录索引i处的值T  current=a[i];//索引i后面的元素依次向前移动一位即可for(int index= i;index<N-1;index++){a[index]=a[index+1];}N--;return current ;}//查找t元素第一次出现的位置public int indexOf(T t){for(int i=0;i<N;i++){if(a[i]==t){return i;}}return -1;}public static void main(String[] args){//创建顺序表对象SequenceList<String>s =new SequenceList<>(10);//测试插入s.insert("姚明");s.insert("小明");s.insert("小王");s.insert(1,"科比");//测试获取String gets=s.get(1);System.out.println("索引1处的结果为:"+gets);//测试删除String removeresult =s.remove(0);System.out.println("删除的元素是:"+removeresult);//测试清空s.reset();System.out.println("清空后的元素个数为:"+s.length());	}
}

时间复杂度 

•  get(i):一次就可以获取到对应的元素，时间复杂度为O(1);
• Insert(int i,T t):每一次插入，都需要把i位置后的元素移动一次，N越大，移动的元素越多，时间复杂度为O(N);
• remove(int i):每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大，移动的元素也越多，时间复杂度为O(N);
• 由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器的扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的节点处，耗时会突增，尤其是元素越多，越明显

链表

定义：链表是一种递归的数据结构，它或者为空(null),或者是含有泛型元素的结点和指向另一条链表的引用。

链表是一种物理存储单元上非连续，非顺序的存储结构，其物理结构不能直观的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点(链表中的每一个元素称为结点)组成，结点可以在运行时动态生成。

我们可以设计一个类，用来描述结点这个事物，用一个属性描述这个结点存储的元素，用来另外一个属性描述这个结点的下一个结点。

类名	Node<T>
构造方法	Node(T t,Node next):创建Node对象
成员变量	T item:存储数据 Node next:指向下一个结点

public class Node<T> {//存储元素public T item;//指向下一个结点public Node next;public Node(T item,Node next){this.item=item;this.next=next;}
public 	static void main(String[] args)
{//构建结点Node<Integer>first=new Node<Integer>(10,null);Node<Integer>second=new Node<Integer>(20,null);Node<Integer>third=new Node<Integer>(30,null);//生成链表first.next=second;second.next=third;	
}
}

单向链表

单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。

 单向链表代码实现

import java.util.Iterator;         //Iterable接口用来表面可以进行迭代
public class LinkList<T> implements Iterable<T> {//记录头结点private Node head;//记录链表的长度private int N;//结点类private class Node{//存储数据T item;//下一个结点Node next;public Node(T item,Node next){this.item=item;this.next=next;}}public LinkList() {//创建结节点this.head=new Node(null,null);//初始化元素个数this.N=0;}//清空链表public void clear(){head.next=null;//使头结点不指向下一个结点this.N=0;}//获取链表的长度public int length(){return N;}//判断链表是否为空public boolean isEmpty(){return N==0;}//获取指定位置i处的元素public T get(int i){//通过循环，从头结点开始往后找，依次找i次，就可以找到对应的元素Node n=head.next;//不断的把n向后变化，直到变化到第i个位置处for(int index=0;index<i;index++){n=n.next;	}return n.item;}//向链表中添加元素tpublic void insert(T t){//找到当前最后一个结点Node n=head;while(n.next!=null){n=n.next;}//创建新结点，保存元素tNode newNode =new Node(t,null);//让当前最后一个结点指向新结点n.next=newNode;//元素的个数加1N++;}//向指定位置i处，添加元素tpublic void insert(int i,T t){//找到i位置前一个节点Node p=head;for(int index=0;index<=i-1;index++){p=p.next;}//找到i位置的节点Node c=p.next;//创建新结点,并且新结点需要指向原来i位置的结点Node newNode =new Node(t,c);//原来i位置的前一个结点指向新结点即可p.next=newNode;//元素的个数+1N++;	}//删除指定位置i处的元素，并返回被删除的元素public T remove(int i){//找到i位置的前一个结点Node p=head;for(int index=0;index<=i-1;i++){p=p.next;}//要找到i位置的结点 Node c=p.next;//找到i位置的下一个结点Node nextNode=c.next;//前一个节点指向下一个结点p.next=nextNode;//元素个数减1N--;return c.item;}//查找元素t在链表中第一次出现的位置public int indexOf(T t) {//从头结点开始，依次找到每一个结点，取出item,和t比较，如果相同，就找到了Node n=head;for(int index=0;n.next!=null;index++){n=n.next;if(n.item==t)return index;}return -1;}public 	Iterator<T> iterator()
{return new LIterator();
}private class 	LIterator implements Iterator{private Node n;public LIterator(){this.n=head;}@Overridepublic boolean hasNext() {return n.next!=null;}@Overridepublic Object next(){n=n.next;return n.item;}
}}

import java.util.Arrays;
public class test{public static void main(String[] args)
{//创建单向链表对象LinkList <String> s1= new LinkList<>();//测试插入s1.insert("姚明");s1.insert("科比");s1.insert("小王");s1.insert(1,"成龙");for(String s:s1){System.out.println(s);}System.out.println("————————————————————————————————————————————————————");//测试获取String getresult =s1.get(1);System.out.println("获取索引1处的结果为:"+getresult);//测试删除String removeresult =s1.remove(0);System.out.println("删除元素是:"+removeresult);//测试清空s1.clear();System.out.println("清空后的线性表中的元素个数为:"+s1.length());
}
}

 双向链表

定义：双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。

 代码实现

import java.util.Iterator;
//Iterable接口用来表面可以进行迭代
public class TowWayLinkList<T> implements Iterable<T> {//首结点private Node head;//尾结点private Node last;//链表的长度private int N;//结点类private class Node{//存储数据public	T item;//指向上一个结点public 	Node pre;//指向下一个结点public Node next;public Node(T item,Node pre,Node next){this.item=item;this.next=next;this.pre=pre;}	}public TowWayLinkList(){//初始化头结点和尾结点this.head=new Node(null,null,null);this.last=null;//刚开始尾结点没有数据//初始化元素个数this.N=0;}//清空链表public void clear(){this.head.next=null;this.head.item=null;this.head.pre=null;this.last=null;this.N=0;}//获取链表长度public int length(){return N;}//判断链表是否为空public boolean isEmpty(){return N==0;}//获取第一个元素public T getFirst(){     if(isEmpty()){return null;}return head.next.item;}//获取最后一个元素public  T getLast(){if(isEmpty()){return null;}return last.item;}//插入元素tpublic void insert(T t){//如果链表为空,1.创建新的结点，2.并让新结点成为尾结点，3.并让头结点指向新结点if(isEmpty()){//1.创建新结点Node newNode=new Node(t,head,null);//2.让新结点成为尾结点last=newNode;//3.让头结点指向新结点head.next=last;	}	else//如果链表不为空{//创建新的结点Node oldlast=last;Node newNode=new Node(t,oldlast,null);//让当前的尾结点指向新结点oldlast.next=newNode;	//让新结点称为尾结点last=newNode;}N++;//元素个数加1}//向指定位置i处插入元素tpublic void insert(int i,T t){//找到i位置的前一个结点Node pre=head;for(int index=0;index<=i-1;index++){pre=pre.next;}//找到i位置的结点Node c=pre.next;//创建新结点Node newNode=new Node(t,pre,c);	//让i位置的前一个结点的下一个结点变为新结点pre.next=newNode;//让i位置的前一个结点变为新结点c.pre=newNode;//元素个数+1	N++;		}public T get(int i){Node n=head.next;for(int index=0;index<i;index++){n=n.next;}return n.item;}//找到元素t在链表中第一次出现的位置public int indexOf(T t) {//从头结点开始，依次找到每一个结点，取出item,和t比较，如果相同，就找到了Node n=head;for(int index=0;n.next!=null;index++){n=n.next;if(n.item==t)return index;}return -1;}//删除指定位置i处的元素，并返回被删除的元素public T remove(int i){//找到i位置的前一个结点Node pre=head;for(int index=0;index<=i-1;i++){pre=pre.next;}//要找到i位置的结点 Node c=pre.next;//找到i位置的下一个结点Node nextNode=c.next;//让i位置的前一个结点的下一个结点变为i位置的下一个结点pre.next=nextNode;//让i位置的后一个节点的上一个结点变为i位置的上一个结点nextNode.pre=pre;//元素个数减1N--;return c.item;}@Overridepublic Iterator<T> iterator() {// TODO Auto-generated method stubreturn new TIterator();}private class 	TIterator implements Iterator{private Node n;public TIterator(){this.n=head;}@Overridepublic boolean hasNext() {return n.next!=null;}@Overridepublic Object next(){n=n.next;return n.item;}}	
}

import java.util.Arrays;
public class test{public static void main(String[] args)
{//创建双向链表对象TowWayLinkList <String> s1= new TowWayLinkList<>();//测试插入s1.insert("姚明");s1.insert("科比");s1.insert("小王");s1.insert(1,"成龙");for(String s:s1){System.out.println(s);}System.out.println("——————————————————————————————————————————————————");System.out.println("第一个元素是"+s1.getFirst());System.out.println("第后一个元素是"+s1.getLast());System.out.println("————————————————————————————————————————————————————");//测试获取String getresult =s1.get(1);System.out.println("获取索引1处的结果为:"+getresult);//测试删除String removeresult =s1.remove(0);System.out.println("删除元素是:"+removeresult);//测试清空s1.clear();System.out.println("清空后的线性表中的元素个数为:"+s1.length());}
}

时间复杂度分析

视频笔记：

• get(int i)：每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)
• insert(int i,T t):每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)
• remove(int i):每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)
• 相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间的大小，或者在存储过程中涉及到扩容等操作，同时它并没有涉及的元素的交换
• 相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询的操作比较多，建议使用顺序表，增删操作比较多，建议使用链表

学习如逆水行舟，不进则退。和小吴一起加油吧！