(顺序表、单链表、双链表)==＞一篇解决!(Java版)

---

一、线性表

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。
线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。

线性表的分类：
线性表中数据存储的方式有两种：顺序存储和链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表，链表又有单链表和双链表两种。

二、顺序表

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

我们用代码实现顺序表,我们应要考虑到成员变量、构造方法、成员方法。
一.成员变量:
我们使用数组来实现顺序表,其成员变量就是要有两个,一个是存储元素的数组,一个是记录当前顺序表有效的长度.
二.构造方法:
创建一个有参的构造方法,来初始化数组的容量和其有效长度
三.成员方法:
1.public void clear()：清空顺序表
2.publicboolean isEmpty()：判断表是否为空，是返回true，否返回false
3.public int length():获取表中元素的个数
4.public T get(int i):获取表中的第i个元素
5.public void insert(int i,T t)：在表的第i个元素之前插入一个值为t的数据元素。
6.public void insert(T t):向表中添加一个元素t(尾插)
7.public T remove(int i):删除表中第i个元素。
8.public int indexOf(T t):返回表中首次出行元素t时的下标。
9.public void resize(int newSize): 当数组满了,根据newSize进行扩容。
10.顺序表的遍历,就要实现Iterable接口
接下来就是代码实现:
具体思路都在代码注释中

import java.util.Iterator;public class SequenceList <T> implements Iterable<T>{//存储元素的数组private T[] eles;//顺序表的长度private int N;//构造方法.创建容量为capacity的SequenceList对象public SequenceList(int capacity) {this.eles = (T[]) new Object[capacity];//这里表示的是有效元素数据this.N = 0;}//空置顺序表public void clear() {this.N = 0;}//判断顺序表是否为空,是返回true,反之返回falsepublic boolean isEmpty() {return N == 0;}//获取顺序表中的元素个数public int length() {return N;}//读取并返回顺序表中的第i个元素的值public T get(int i) {return eles[i];}//在第i个元素之前插入一个值为t的数据元素public void insert(int i, T t) {//先判断容量是否足够if (N == eles.length) {//不够则扩容,一般是原数组长度的两倍resize(2 * N);}//需要吧i位置元素向后移动一位即可for (int index = N; index >= i; index--) {eles[index] = eles[index - 1];}//然后把t元素放进来eles[i] = t;//有效元素+1N++;}//向线性表中添加一个元素tpublic void insert(T t) {//先判断容量是否足够if (N == eles.length) {//不够则扩容,一般是原数组长度的两倍resize(2 * N);}eles[N++] = t;}//扩容根据newSize,重置eles的大小public void resize(int newSize) {//定义一个辅助数组,备份elesT[] arr = eles;//创建新数组eles = (T[]) new Object[newSize];//把原数组的值复制过去for (int i = 0; i < N; i++) {eles[i] = arr[i];}}//删除并返回线性表中第i个数据元素public T remove(int i) {//先记录i索引处的值T temp = eles[i];//将i数据后面的数据向前覆盖for (int index = i; index <= N; index++) {eles[i] = eles[i + 1];}//减少有效长度N--;//如果有效长度小于数组长度的四分之一,就要缩值,缩小二分之一if (N < eles.length / 4) {resize(eles.length / 2);}return temp;}//查找t元素第一次出现的位置,没有则返回-1public int indexOf(T t) {//遍历顺序表,依次比对for (int i = 0; i < N; i++) {if (eles[i].equals(t))return i;}return  -1;}//打印遍历顺序表
//重写iterator方法@Overridepublic Iterator iterator() {return new SIterator();}//构架一个内部类来实现Iterator接口private class SIterator implements Iterator{private int cur;public SIterator(){this.cur=0;}//是否还有下一个元素@Overridepublic boolean hasNext() {return cur<N;}//下一个元素@Overridepublic T next() {return eles[cur++];}}}

测试一下我们实现的顺序表的功能:

三、单链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
链表顾名思义我们可以想象一下链子的样子,每一段就是一个节点,没有固定形状比较灵活,我们上图看一下:

像这样每个节点相连接.
我们把它具体的实现一下,更容易理解:

每个节点都是单独的个体,我们可以将其连接起来变为链表,我们先来定义一下节点类:

private class Node {//存储数据T data;//下一个节点Node next;//构造节点public Node(T data, Node next) {this.data = data;this.next = next;}

接着我们还是要对其进行设计:
一、成员变量:
1.private Node head:记录首结点
2.private int N:记录链表的长度
二、构造方法:
LinkList()：创建LinkList对象
三、成员方法:
1.public void clear()：空置链表
2.publicboolean isEmpty()：判断表是否为空，是返回true，否返回false
3.public int length():获取表中元素的个数
4.public T get(int i):读取并返回表中的第i个元素的值
5.public void insert(T t)：往表中添加一个元素；
6.public void insert(int i,T t)：在表的第i个元素之前插入一个值为t的数据元素。
7.public T remove(int i):删除并返回表中第i个数据元素。
8.public int indexOf(T t):返回表中首次t数据元素的位序号，若不存在，则返回-1
9.链表遍历=>实现Iterator接口
代码实现:

import java.util.Iterator;public class LinkList<T> implements Iterable<T>{//记录首节点private Node head;//记录链表的长度private int N;//节点类private class Node {//存储数据T data;//下一个节点Node next;//构造节点public Node(T data, Node next) {this.data = data;this.next = next;}}public LinkList() {//初始化头结点this.head = new Node(null, null);//初始化元素个数this.N = 0;}//空置链表public void clear() {head.next = null;N = 0;}//判断链表表是否为空public boolean isEmpty() {return N == 0;}//获取元素个数public int length() {return N;}//获取i位置的元素public T get(int i) {//安全检查if (i < 0 || i >= N) {throw new RuntimeException("位置不合法！");}//遍历链表即可Node n = head.next;for (int index = 0; index < i; index++) {n = n.next;}return n.data;}//添加元素(尾插法)public void insert(T t){Node n = head;//循环至尾节点while(n.next != null) {n = n.next;}//此时就是尾节点了,直接插入//构建值为t的节点Node newNode = new Node(t, null);n.next = newNode;//有效长度+1N++;}//在i位置,插入一个值为t的数据元素//1.找到i位置的前一个节点//2.使i-1位置的节点指向新节点,新节点在指向原本i位置的节点即可public void insert(int i, T t) {//安全检查if (i < 0 || i > N){throw new RuntimeException("位置不合法！");}//查找到i - 1位置的节点Node n = head;for (int index = 0; index <= i - 1; i++) {n = n.next;}//创建新节点Node newNode = new Node(t, null);//保留原本i位置处的节点Node cur = n.next;//i - 1位置的节点指向新节点n.next = newNode;//新节点指向原本i位置的节点newNode.next = cur;//有效长度+1N++;}//删除第i个数据元素//将第i - 1位置的元素,指向i + 1位置的节点即可public T remove(int i) {//安全检查if (i < 0 || i >= N){throw new RuntimeException("位置不合法");}//找到第i - 1位置的元素Node n = head;for (int index = 0; index <= i - 1; index++) {n = n.next;}//记录i位置节点的值Node cur = n.next;//i - 1位置的节点指向i + 1位置的节点n.next = cur.next;//有效长度-1N--;//返回被删除的值return cur.data;}//t元素数据首先出现时的位序号,没找到返回-1public int indexOf(T t) {//遍历查找Node n = head;for (int i = 0; i < N; i++) {n = n.next;if (n.data.equals(t)) {return i;}}return -1;}//重写Iterator接口方法@Overridepublic Iterator<T> iterator() {return new LIterator();}//定义内部类,实现遍历private class LIterator implements Iterator<T> {private Node n;public LIterator() {this.n = head;}@Overridepublic boolean hasNext() {return n.next != null;}@Overridepublic T next() {n = n.next;return n.data;}}
}

测试一下:

四、双链表

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

接下来我们实现一下双链表:
一、成员变量:
1.private Node first:首结点
2.private Node last:尾节点
2.private int N:记录链表的长度
二、构造方法:
TowWayLinklist()：创建TowWayLinklist对象
三、成员方法:
1.public void clear()：空置链表
2.publicboolean isEmpty()：判断表是否为空，是返回true，否返回false
3.public int length():获取表中元素的个数
4.public T get(int i):读取并返回表中的第i个元素的值
5.public void insert(T t)：往表中添加一个元素；
6.public void insert(int i,T t)：在表的第i个元素之前插入一个值为t的数据元素。
7.public T remove(int i):删除并返回表中第i个数据元素。
8.public int indexOf(T t):返回表中首次t数据元素的位序号，若不存在，则返回-1
9.public T getFirst():获取第一个元素
10.public T getLast():获取最后一个元素
9.链表遍历=>实现Iterator接口
代码实现:

import java.util.Iterator;public class TowWayLinklist<T> implements Iterable<T> {//首结点private Node head;//最后一个结点private Node last;//链表的长度private int N;//结点类private class Node{public Node(T item, Node pre, Node next) {this.item = item;this.pre = pre;this.next = next;}//存储数据public T item;//指向上一个结点public Node pre;//指向下一个结点public Node next;}public TowWayLinklist() {//初始化头结点和尾结点this.head = new Node(null,null,null);this.last=null;//初始化元素个数this.N=0;}//清空链表public void clear(){this.head.next=null;this.head.pre=null;this.head.item=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){if (isEmpty()){//如果链表为空：//创建新的结点Node newNode = new Node(t,head, null);//让新结点称为尾结点last=newNode;//让头结点指向尾结点head.next=last;}else {//如果链表不为空Node oldLast = last;//创建新的结点Node newNode = new Node(t, oldLast, null);//让当前的尾结点指向新结点oldLast.next=newNode;//让新结点称为尾结点last = newNode;}//元素个数+1N++;}//向指定位置i处插入元素tpublic void insert(int i,T t){//找到i位置的前一个结点Node pre = head;for(int index=0;index<i;index++){pre=pre.next;}//找到i位置的结点Node curr = pre.next;//创建新结点Node newNode = new Node(t, pre, curr);//让i位置的前一个结点的下一个结点变为新结点pre.next=newNode;//让i位置的前一个结点变为新结点curr.pre=newNode;//元素个数+1N++;}//获取指定位置i处的元素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){Node n = head;for(int i=0;n.next!=null;i++){n=n.next;if (n.next.equals(t)){return i;}}return -1;}//删除位置i处的元素，并返回该元素public T remove(int i){//找到i位置的前一个结点Node pre = head;for(int index=0;index<i;index++){pre=pre.next;}//找到i位置的结点Node curr = pre.next;//找到i位置的下一个结点Node nextNode= curr.next;//让i位置的前一个结点的下一个结点变为i位置的下一个结点pre.next=nextNode;//让i位置的下一个结点的上一个结点变为i位置的前一个结点nextNode.pre=pre;//元素的个数-1N--;return curr.item;}@Overridepublic Iterator<T> iterator() {return 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;}}}

测试一下:

---