【专题二】线性表

1.简介

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。

前驱元素：
若A元素在B元素的前面，则称A为B的前驱元素
后继元素：
若B元素在A元素的后面，则称B为A的后继元素
线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。
1. 第一个数据元素没有前驱，这个数据元素被称为头结点；
2. 最后一个数据元素没有后继，这个数据元素被称为尾结点；
3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
如果把线性表用数学语言来定义，则可以表示为(a1,...ai-1,ai,ai+1,...an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素

线性表的分类：
线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。

2.顺序表

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

2.1 顺序表的实现

顺序表API设计：

类名	SequenceList
构造方法	SequenceList(int capacity)：创建容量为capacity的SequenceList对象
成员方法	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):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
成员变量	1.private T[] eles：存储元素的数组 2.private int N:当前线性表的长度

顺序表的代码实现：

  1 package cn.itcast.algorithm.Demo.linear;
  2 
  3 
  4 import cn.itcast.algorithm.linear.SequenceList;
  5 
  6 import java.util.Iterator;
  7 import java.util.Spliterator;
  8 import java.util.function.Consumer;
  9 
 10 public class SequenceListDemo<T> implements Iterable<T> {
 11     //成员变量
 12     /*
 13       1.private T[] eles：存储元素的数组
 14       2.private int N:当前线性表的长度
 15     */
 16     private T[] eles;
 17     private int N;
 18 
 19 
 20     //构造方法
 21     /*
 22     SequenceList(int capacity)：创建容量为capacity的SequenceList对象
 23      */
 24     public SequenceListDemo(int capacity) {
 25         //初始化数组
 26         this.eles = (T[]) new Object[capacity];
 27         //初始化长度
 28         this.N = 0;
 29     }
 30 
 31     //成员方法
 32    /*
 33         1.public void clear()：空置线性表
 34         2.public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false
 35         3.public int length():获取线性表中元素的个数
 36         4.public T get(int i):读取并返回线性表中的第i个元素的值
 37         5.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。
 38         6.public void insert(T t):向线性表中添加一个元素t
 39         7.public T remove(int i):删除并返回线性表中第i个数据元素。
 40         8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
 41     */
 42 
 43     //1.public void clear()：空置线性表
 44     public void clear() {
 45         this.N = 0;
 46     }
 47 
 48     //2.public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false
 49     public boolean isEmpty() {
 50         return N == 0;
 51     }
 52 
 53     //3.public int length():获取线性表中元素的个数
 54     public int length() {
 55         return N;
 56     }
 57 
 58     //4.public T get(int i):读取并返回线性表中的第i个元素的值
 59     public T get(int i) {
 60         return eles[i];
 61     }
 62 
 63     //5.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。
 64     public void insert(int i, T t) {
 65         //扩容
 66         if (N == eles.length) {
 67             resize(2 * eles.length);
 68         }
 69 
 70         //先把i索引处的元素及其后面的元素依次向后移动一位
 71         for (int index = N; index > i; index--) {
 72             eles[index] = eles[index - 1];
 73         }
 74         //再把t元素放到i索引处即可
 75         eles[i] = t;
 76 
 77         //元素个数+1
 78         N++;
 79     }
 80 
 81     //6.public void insert(T t):向线性表中添加一个元素t.添加在尾部
 82     public void insert(T t) {
 83 
 84         if (N == eles.length) {
 85             resize(2 * eles.length);
 86         }
 87 
 88         eles[N++] = t;
 89     }
 90 
 91     //根据参数newSize，重置eles的大小
 92     public void resize(int newSize) {
 93 
 94         //定义一个临时数组，指向原数组
 95         T[] temp = eles;
 96         //创建新数组
 97         eles = (T[]) new Object[newSize];
 98         //把原数组的数据拷贝到新数组即可
 99         for (int i = 0; i < N; i++) {
100             eles[i] = temp[i];
101         }
102     }
103 
104     //7.public T remove(int i):删除并返回线性表中第i个数据元素。
105     public T remove(int i) {
106         T current = eles[i];
107         //先把i索引处的元素及其后面的元素依次向前移动一位
108         for (int index = N; index > i; index--) {
109             eles[index - 1] = eles[index];
110         }
111         //元素个数-1
112         N--;
113         //缩容
114         if (N < eles.length / 4) {
115             resize(eles.length / 2);
116         }
117         return current;
118     }
119 
120     //8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
121     public int indexOf(T t) {
122         for (int i = 0; i < eles.length; i++) {
123             if (eles[i].equals(t)) {
124                 return i;
125             }
126         }
127         return -1;
128     }
129 
130 
131     @Override
132     public Iterator<T> iterator() {
133         return new SIterator();
134     }
135 
136     private class SIterator implements Iterator{
137         private int cusor;
138         public SIterator(){
139             this.cusor=0;
140         }
141         @Override
142         public boolean hasNext() {
143             return cusor<N;
144         }
145 
146         @Override
147         public Object next() {
148             return eles[cusor++];
149         }
150     }
151 }

View Code

测试类：

 1 package cn.itcast.algorithm.DemoTest.sortTest.linearTest;
 2 
 3 import cn.itcast.algorithm.Demo.linear.SequenceListDemo;
 4 
 5 public class SequenceListDemoTest {
 6     public static void main(String[] args) {
 7         //创建对象
 8         SequenceListDemo<String> s = new SequenceListDemo<>(10);
 9         //插入元素
10         s.insert("中秋节");
11         s.insert("国庆节");
12         s.insert("元宵节");
13         s.insert("清明节");
14 
15 
16         System.out.println("------------------------------");
17         //遍历元素
18         System.out.println("遍历元素");
19         for (String s1 :s){
20             System.out.println(s1);
21         }
22 
23         System.out.println("------------------------------");
24         boolean sEmpty = s.isEmpty();
25         System.out.println(sEmpty);
26 
27         System.out.println("------------------------------");
28         //移除元素
29         System.out.println("移除元素");
30         s.remove(3);
31         for (String s1 :s){
32             System.out.println(s1);
33         }
34 
35         System.out.println("------------------------------");
36         //在线性表的第i个元素之前插入一个值为t的数据元素
37         System.out.println("在线性表的第i个元素之前插入一个值为t的数据元素");
38         s.insert(0,"劳动节");
39         s.insert(1,"儿童节");
40         for (String s1 :s){
41             System.out.println(s1);
42         }
43 
44 
45     }
46 
47 }

View Code

2.2. 顺序表的遍历

一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。
在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则
需要做如下操作：
1.让SequenceList实现Iterable接口，重写iterator方法；
2.在SequenceList内部提供一个内部类SIterator,实现Iterator接口，重写hasNext方法和next方法；

2.3 顺序表的容量可变

在之前的实现中，当我们使用SequenceList时，先new SequenceList(5)创建一个对象，创建对象时就需要指定容器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数
据，则会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的伸缩性。
考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小，那我们需要考虑什么时候需要改变数组的大小？
1.添加元素时：
添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。

 1  //6.public void insert(T t):向线性表中添加一个元素t.添加在尾部
 2     public void insert(T t) {
 3         if (N == eles.length) {
 4             resize(2 * eles.length);
 5         }
 6         eles[N++]=t;
 7     }
 8 
 9     //根据参数newSize，重置eles的大小
10     public void resize(int newSize) {
11         //定义一个临时数组，指向原数组
12         T[] temp = eles;
13         //创建新数组
14         eles = (T[]) new java.lang.Object[newSize];
15         //把原数组的数据拷贝到新数组即可
16         for (int i = 0; i < N; i++) {
17             eles[i] = temp[i];
18         }
19     }

2.移除元素时：
移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。

 1 //7.public T remove(int i):删除并返回线性表中第i个数据元素。
 2     public T remove(int i) {
 3         T current = eles[i];
 4         //先把i索引处的元素及其后面的元素依次向前移动一位
 5         for (int index = N; index > i; index--) {
 6             eles[index - 1] = eles[index];
 7         }
 8         //元素个数-1
 9         N--;
10         //缩容
11         if (N < eles.length / 4) {
12             resize(eles.length/2);
13         }
14         return current;
15     }

2.4 顺序表的时间复杂度

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

2.5 java中ArrayList实现

java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。
1.是否用数组实现；
2.有没有扩容操作；
3.有没有提供遍历方式

3.链表

之前我们已经使用顺序存储结构实现了线性表，我们会发现虽然顺序表的查询很快，时间复杂度为O(1),但是增删的效率是比较低的，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？有，我们可以使用另外一种存储结构实现线性表，链式存储结构。链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。

那我们如何使用链表呢？按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个结点存储的元素，用来另外一个属性描述这个结点的下一个结点。

结点API设计：

类名	Node
构造方法	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) throws Exception {
    //构建结点
    Node<Integer> first = new Node<Integer>(11, null);
    Node<Integer> second = new Node<Integer>(13, null);
    Node<Integer> third = new Node<Integer>(12, null);
    Node<Integer> fourth = new Node<Integer>(8, null);
    Node<Integer> fifth = new Node<Integer>(9, null);
    //生成链表
    first.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = fifth;
}

3.1单向链表

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

3.1.1 单向链表API设计

类名	LinkList
构造方法	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):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
成员内部类	private class Node:结点类
成员变量	1.private Node head:记录首结点 2.private int N:记录链表的长度

3.1.2 单向链表代码实现

  1 package cn.itcast.algorithm.Demo.linear;
  2 
  3 
  4 import cn.itcast.algorithm.linear.LinkList;
  5 
  6 
  7 import java.util.Iterator;
  8 import java.util.Spliterator;
  9 import java.util.function.Consumer;
 10 
 11 public class LinkListDemo<T> implements Iterable<T> {
 12 
 13     /*public static void main(String[] args) {
 14         //构建节点
 15         Node<Integer> first = new Node<Integer>(11, null);
 16         Node<Integer> second = new Node<Integer>(22, null);
 17         Node<Integer> third = new Node<Integer>(33, null);
 18         Node<Integer> fourth = new Node<Integer>(44, null);
 19         Node<Integer> fifth = new Node<Integer>(55, null);
 20 
 21 
 22         //生成链表
 23         first.next= second;
 24     }*/
 25 
 26 
 27     //成员变量
 28     private Node head;//记录首结点
 29     private int N;//记录链表的长度
 30 
 31     //成员内部类
 32     //结点类
 33     private class Node {
 34         //存储数据
 35         T item;
 36         //下一个结点
 37         Node next;
 38 
 39         public Node(T item, LinkListDemo.Node next) {
 40             this.item = item;
 41             this.next = next;
 42         }
 43 
 44     }
 45 
 46     //构造方法
 47     public LinkListDemo() {
 48         //初始化头结点、
 49         this.head = new LinkListDemo.Node(null, null);
 50         //初始化元素个数
 51         this.N = 0;
 52     }
 53 
 54 
 55     //成员方法
 56 
 57     //1.public void clear()：空置线性表
 58     public void clear() {
 59         head.next = null;
 60         this.N = 0;
 61     }
 62 
 63     //2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false
 64     public boolean isEmpty(){
 65         return N == 0;
 66     }
 67 
 68     //3.public int length():获取线性表中元素的个数
 69     public int length(){
 70         return N;
 71     }
 72 
 73     //4.public T get(int i):读取并返回线性表中的第i个元素的值
 74     public T get(int i){
 75         Node pre = head;
 76         for (int index = 0; index <i ; index++) {
 77             pre = pre.next;
 78 
 79         }
 80         return pre.item;
 81     }
 82 
 83     //5.public void insert(T t)：往线性表中添加一个元素；
 84     public void insert(T t){
 85         //找到当前最后一个结点
 86        Node pre = head;
 87        while(pre.next != null){
 88            pre= pre.next;
 89        }
 90         //创建新结点，保存元素t
 91         Node newNode = new Node(t, null);
 92         //让当前最后一个结点指向新结点
 93         pre.next=newNode;
 94         //元素的个数+1
 95         N++;
 96     }
 97 
 98     //6.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。
 99     public void insert(int i,T t){
100         Node pre  = head;
101         for (int index = 0; index <i ; index++) {
102             pre= pre.next;
103         }
104         //找到i位置的结点
105         Node curr = pre.next;
106         //创建新结点，并且新结点需要指向原来i位置的结点
107         Node newNode = new Node(t, curr);
108         //原来i位置的前一个节点指向新结点即可
109         pre.next = newNode;
110 //        pre.next=newNode.next.next;
111         //长度+1
112         N ++;
113     }
114 
115     //7.public T remove(int i):删除并返回线性表中第i个数据元素。
116     public T remove(int i){
117         Node pre  = head;
118         for (int index = 0; index <i ; index++) {
119             pre= pre.next;
120         }
121         //找到i位置的结点
122         Node curr = pre.next;
123         //找到当前位置的下一节点
124         Node nextNode = curr.next;
125         //把i之前位置的指针指向当前位置的下一元素
126         pre.next = nextNode;
127         //长度-1
128         N--;
129         //返回元素
130         return curr.item;
131     }
132 
133     //8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则 返回-1。
134     public int indexOf(T t){
135         Node pre  = head;
136         for (int index = 0; index <N; index++) {
137             pre= pre.next;
138             if (pre.item.equals(t)) {
139                 return index;
140             }
141         }
142         return -1;
143     }
144 
145     @Override
146     public Iterator<T> iterator() {
147         return new LIterator();
148     }
149 
150     @Override
151     public void forEach(Consumer<? super T> action) {
152 
153     }
154 
155     @Override
156     public Spliterator<T> spliterator() {
157         return null;
158     }
159     private class LIterator implements Iterator{
160         private LinkListDemo.Node n;
161         public LIterator(){
162             this.n=head;
163         }
164 
165         @Override
166         public boolean hasNext() {
167             return n.next!=null;
168         }
169 
170         @Override
171         public Object next() {
172             n = n.next;
173             return n.item;
174         }
175     }
176 }

View Code

测试：

 1 package cn.itcast.algorithm.DemoTest.sortTest.linearTest;
 2 
 3 import cn.itcast.algorithm.Demo.linear.LinkListDemo;
 4 import cn.itcast.algorithm.Demo.linear.SequenceListDemo;
 5 
 6 import java.util.ArrayList;
 7 
 8 public class LinkedListDemoTest {
 9     public static void main(String[] args) {
10         //创建对象
11         LinkListDemo<String> s = new LinkListDemo<String>();
12         //插入元素
13         s.insert("中秋节");
14         s.insert("国庆节");
15         s.insert("元宵节");
16         s.insert("清明节");
17 
18         System.out.println("------------------------------");
19         //遍历元素
20         System.out.println("遍历元素");
21         System.out.println("------------------------------");
22 
23         for (String s1 : s) {
24             System.out.println(s1);
25         }
26 
27         System.out.println("------------------------------");
28         boolean sEmpty = s.isEmpty();
29         System.out.println(sEmpty);
30 
31         System.out.println("------------------------------");
32         //移除元素
33         System.out.println("移除元素");
34         s.remove(3);
35         for (String s1 : s) {
36             System.out.println(s1);
37         }
38 
39         System.out.println("------------------------------");
40         //在线性表的第i个元素之前插入一个值为t的数据元素
41         System.out.println("在线性表的第i个元素之前插入一个值为t的数据元素");
42         s.insert(0, "劳动节");
43         s.insert(1, "儿童节");
44         for (String s1 : s) {
45             System.out.println(s1);
46         }
47 
48         System.out.println("------------------------------");
49         //返回线性表中首次出现的指定的数据元素的位序号
50         System.out.println("返回线性表中首次出现的指定的数据元素的位序号");
51         String s1 = s.get(1);
52         System.out.println(s1);
53     }
54 
55 }

View Code

结果：

------------------------------
遍历元素
------------------------------
中秋节
国庆节
元宵节
清明节
------------------------------
false
------------------------------
移除元素
中秋节
国庆节
元宵节
------------------------------
在线性表的第i个元素之前插入一个值为t的数据元素
劳动节
儿童节
中秋节
国庆节
元宵节
------------------------------
返回线性表中首次出现的指定的数据元素的位序号
劳动节

3.2.双向链表

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

按照面向对象的思想，我们需要设计一个类，来描述结点这个事物。由于结点是属于链表的，所以我们把结点类作为链表类的一个内部类来实现。

3.2.1 结点API设计

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

3.2.2.双向链表API设计

类名	TowWayLinkList
构造方法	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):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。 9.public T getFirst():获取第一个元素 10.public T getLast():获取最后一个元素
成员内部类	private class Node:结点类
成员变量	1.private Node first:记录首结点 2.private Node last:记录尾结点 2.private int N:记录链表的长度

3.2.3.双向链表的实现

  1 package cn.itcast.algorithm.Demo.linear;
  2 
  3 import cn.itcast.algorithm.linear.TowWayLinkList;
  4 import jdk.nashorn.internal.ir.Node;
  5 
  6 import java.util.Iterator;
  7 
  8 public class TwoWayLinkListDemo<T> implements Iterable<T> {
  9     //成员变量
 10   /*
 11     private Node first:记录首结点
 12     private Node last:记录尾结点
 13     private int N:记录链表的长度
 14     */
 15     //首结点
 16     private Node head;
 17     //尾结点
 18     private Node last;
 19     //链表的长度
 20     private int N;
 21 
 22     //成员内部类 private class Node:结点类
 23     private class Node {
 24         public Node(T item, Node pre, Node next) {
 25             this.item = item;
 26             this.pre = pre;
 27             this.next = next;
 28         }
 29 
 30         //存储数据
 31         public T item;
 32         //指向上一个结点
 33         public Node pre;
 34         //指向下一个结点
 35         public Node next;
 36     }
 37 
 38     //构造方法 TowWayLinkList()：创建TowWayLinkList对象
 39     public TwoWayLinkListDemo() {
 40         //初始化头结点和尾结点
 41         this.head = new Node(null, null, null);
 42         this.last = null;
 43         //初始化元素个数
 44         this.N = 0;
 45     }
 46 
 47 
 48     //成员方法
 49     //1.public void clear()：空置线性表
 50     public void clear() {
 51         //头结点、未节点为null,元素个数为0
 52         this.head.pre = null;
 53         this.head.next = null;
 54         this.head.item = null;
 55         this.last = null;
 56         this.N = 0;
 57     }
 58 
 59     //2.public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false
 60     public boolean isEmpty() {
 61         return N == 0;
 62     }
 63 
 64     //3.public int length():获取线性表中元素的个数
 65     public int length() {
 66         return N;
 67     }
 68 
 69     //4.public T get(int i):读取并返回线性表中的第i个元素的值
 70     public T get(int i) {
 71         Node n = head.next;
 72         for (int index = 0; index < i - 1; index++) {
 73             n = n.next;
 74         }
 75         return n.item;
 76     }
 77 
 78     //5.public void insert(T t)：往线性表中添加一个元素；
 79     public void insert(T t) {
 80         if (isEmpty()) {
 81             //如果链表为空
 82 
 83             //创建新的结点
 84             Node newNode = new Node(t, head, null);
 85             //让新结点称为尾结点
 86             last = newNode;
 87             //让头结点指向尾结点
 88             head.next = last;
 89 
 90         } else {
 91             //如果链表不为空
 92 
 93             Node oldLast = last;
 94             //创建新节点
 95             Node newNode = new Node(t, oldLast, null);
 96             //让当前的尾结点指向新结点
 97             oldLast.next = newNode;
 98             //让新结点称为尾结点
 99             last = newNode;
100         }
101         //元素个数+1
102         N++;
103 
104     }
105 
106     //6.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。
107     public void insert(int i, T t) {
108 
109         //找到i位置的前一个结点
110        Node pre = head;
111         for(int index=0;index<i;index++){
112             pre=pre.next;
113         }
114         //找到i位置的结点
115         Node curr = pre.next;
116         //创建新结点
117        Node newNode = new Node(t, pre, curr);
118         //让i位置的前一个结点的下一个结点变为新结点
119         pre.next=newNode;
120         //让i位置的前一个结点变为新结点
121         curr.pre=newNode;
122         //元素个数+1
123         N++;
124 
125     }
126 
127     //7.public T remove(int i):删除并返回线性表中第i个数据元素。
128     public T remove(int i) {
129         //如果链表为空
130         if (isEmpty()) {
131             return null;
132         }
133         Node pre = head.next;
134         for (int index = 0; index < i; index++) {
135             pre = pre.next;
136         }
137         //找到i位置的结点
138         Node curr = pre.next;
139         //找到i位置的下一个结点
140         Node nextNode = curr.next;
141         //让i位置的前一个结点的下一个结点变为i位置的下一个结点
142         pre.next = nextNode;
143         //让i位置的下一个结点的上一个结点变为i位置的前一个结点
144         nextNode.pre = pre;
145         //元素的个数-1
146         N--;
147         return curr.item;
148     }
149 
150     //8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1。
151     public int indexOf(T t) {
152         Node n = head.next;
153         for (int index = 0; index < N; index++) {
154             n = n.next;
155             if (n.equals(t)) {
156                 return index;
157             }
158         }
159         return -1;
160     }
161 
162 
163     //9.public T getFirst():获取第一个元素
164     public T getFirst() {
165         //如果链表为null
166         if (isEmpty()) {
167             return null;
168         }
169         return head.next.item;
170     }
171 
172     //10.public T getLast():获取最后一个元素
173     public T getLast() {
174         //如果链表为null
175         if (isEmpty()) {
176             return null;
177         }
178         return last.item;
179     }
180 
181     @Override
182     public Iterator<T> iterator() {
183         return new TIterator();
184     }
185 
186     private class TIterator implements Iterator{
187         private TwoWayLinkListDemo.Node n;
188         public TIterator(){
189             this.n=head;
190         }
191         @Override
192         public boolean hasNext() {
193             return n.next!=null;
194         }
195 
196         @Override
197         public Object next() {
198             n=n.next;
199             return n.item;
200         }
201     }
202 }

View Code

测试：

 1 package cn.itcast.algorithm.DemoTest.sortTest.linearTest;
 2 
 3 import cn.itcast.algorithm.Demo.linear.TwoWayLinkListDemo;
 4 
 5 
 6 public class TowWayLinkListDemoTest {
 7 
 8     public static void main(String[] args) {
 9         //创建双向链表对象
10         TwoWayLinkListDemo<String> sl = new TwoWayLinkListDemo();
11         //测试插入
12         sl.insert("姚明");
13         sl.insert("科比");
14         sl.insert("麦迪");
15         sl.insert(1,"詹姆斯");
16 
17         for (String s : sl) {
18             System.out.println(s);
19         }
20 
21         System.out.println("--------------------------------------");
22         System.out.println("第一个元素是："+sl.getFirst());
23         System.out.println("最后一个元素是："+sl.getLast());
24 
25         System.out.println("------------------------------------------");
26 
27         //测试获取
28         String getResult = sl.get(1);
29         System.out.println("获取索引1处的结果为："+getResult);
30         //测试删除
31         String removeResult = sl.remove(0);
32         System.out.println("删除的元素是："+removeResult);
33         //测试清空
34         sl.clear();
35         System.out.println("清空后的线性表中的元素个数为:"+sl.length());
36 
37 
38     }
39 }

View Code

结果：

姚明
詹姆斯
科比
麦迪
--------------------------------------
第一个元素是：姚明
最后一个元素是：麦迪
------------------------------------------
获取索引1处的结果为：姚明
删除的元素是：詹姆斯
清空后的线性表中的元素个数为:0

3.3 链表的复杂度分析

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

4.栈

4.1 栈概述

栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

4.2 栈的实现

4.2.1 栈API设计

类名	Stack
构造方法	Stack)：创建Stack对象
成员方法	1.public boolean isEmpty()：判断栈是否为空，是返回true，否返回false 2.public int size():获取栈中元素的个数 3.public T pop():弹出栈顶元素 4.public void push(T t)：向栈中压入元素t
成员变量	1.private Node head:记录首结点 2.private int N:当前栈的元素个数

4.2.2 栈代码实现

 1 package cn.itcast.algorithm.DemoTest.sortTest.linearTest;
 2 
 3 import java.util.Iterator;
 4 
 5 public class StackDemo<T> implements Iterable<T> {
 6     //成员变量
 7 
 8     //记录首结点
 9     private Node head;
10     //栈中元素的个数
11     private int N;
12 
13     //构造方法
14     private class Node {
15         public T item;
16         public Node next;
17 
18         public Node(T item, Node next) {
19             this.item = item;
20             this.next = next;
21         }
22     }
23 
24     //构造方法
25     public StackDemo() {
26         this.head = new Node(null, null);
27         this.N = 0;
28     }
29 
30 
31     //成员方法
32 
33     //1.public boolean isEmpty()：判断栈是否为空，是返回true，否返回false
34     public boolean isEmpty() {
35         return N == 0;
36     }
37 
38     //2.public int size():获取栈中元素的个数
39     public int size() {
40         return N;
41     }
42 
43     //3.public T pop():弹出栈顶元素
44     public T pop() {
45         //找到首结点指向的第一个结点
46         Node oldFirst = head.next;
47         if (oldFirst == null) {
48             return null;
49         }
50         //让首结点指向原来第一个结点的下一个结点
51         head.next = oldFirst.next;
52         //元素个数-1；
53         N--;
54         return oldFirst.item;
55     }
56 
57     //4.public void push(T t)：向栈中压入元素t
58     public void push(T t) {
59         //找到首结点指向的第一个结点
60         Node oldFirst = head.next;
61         //创建新结点
62         Node newNode = new Node(t, null);
63         //让首结点指向新结点
64         head.next = newNode;
65         //让新结点指向原来的第一个结点
66         newNode.next = oldFirst;
67         //元素个数+1；
68         N++;
69     }
70     @Override
71     public Iterator<T> iterator() {
72         return new SIterator();
73     }
74 
75     private class SIterator implements Iterator{
76         private Node n;
77 
78         public SIterator(){
79             this.n=head;
80         }
81 
82         @Override
83         public boolean hasNext() {
84             return n.next!=null;
85         }
86 
87         @Override
88         public Object next() {
89             n = n.next;
90             return n.item;
91         }
92     }
93 }

View Code

测试：

 1 public class StackDemoTest {
 2     public static void main(String[] args) {
 3         //创建栈对象
 4         StackDemo<String> stack = new StackDemo<>();
 5 
 6         //测试压栈
 7         stack.push("a");
 8         stack.push("b");
 9         stack.push("c");
10         stack.push("d");
11 
12         for (String item : stack) {
13             System.out.println(item);
14         }
15         System.out.println("------------------------------");
16         //测试弹栈
17         String result1 = stack.pop();
18         System.out.println("弹出的元素是："+result1);
19         String result2 = stack.pop();
20         System.out.println("弹出的元素是："+result2);
21         System.out.println("剩余的元素个数："+stack.size());
22 
23     }
24 }

View Code

结果：

d
c
b
a
------------------------------
弹出的元素是：d
弹出的元素是：c
剩余的元素个数：2

5.队列

队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。

5.1 队列的API设计

类名	Queue
构造方法	Queue()：创建Queue对象
成员方法	1.public boolean isEmpty()：判断队列是否为空，是返回true，否返回false 2.public int size():获取队列中元素的个数 3.public T dequeue():从队列中拿出一个元素 4.public void enqueue(T t)：往队列中插入一个元素
成员变量	1.private Node head:记录首结点 2.private int N:当前栈的元素个数 3.private Node last:记录最后一个结点

5.2 队列的实现

  1 package cn.itcast.algorithm.Demo.linear;
  2 
  3 
  4 import cn.itcast.algorithm.linear.Queue;
  5 
  6 import java.util.Iterator;
  7 
  8 public class QueueDemo<T> implements Iterable<T> {
  9     //成员变量
 10 
 11     //记录首结点
 12     private Node head;
 13     //记录最后一个结点
 14     private Node last;
 15     //记录队列中元素的个数
 16     private int N;
 17 
 18     private class Node {
 19         public T item;
 20         public Node next;
 21 
 22         public Node(T item, Node next) {
 23             this.item = item;
 24             this.next = next;
 25         }
 26     }
 27 
 28     //构造方法
 29     public QueueDemo() {
 30         this.head = new Node(null, null);
 31         this.last = null;
 32         this.N = 0;
 33     }
 34 
 35     //成员方法
 36     //1.public boolean isEmpty()：判断队列是否为空，是返回true，否返回false
 37     public boolean isEmpty() {
 38         return N == 0;
 39     }
 40 
 41     //2.public int size():获取队列中元素的个数
 42     public int size() {
 43         return N;
 44     }
 45 
 46     //3.public T dequeue():从队列中拿出一个元素
 47     public T dequeue() {
 48         if (isEmpty()) {
 49             return null;
 50         }
 51         Node oldFirst = head.next;
 52         head.next = oldFirst.next;
 53         N--;
 54 
 55         //因为出队列其实是在删除元素，因此如果队列中的元素被删除完了，需要重置last=null;
 56         if (isEmpty()) {
 57             last = null;
 58         }
 59         return oldFirst.item;
 60     }
 61 
 62     //4.public void enqueue(T t)：往队列中插入一个元素
 63     public void enqueue(T t) {
 64         if (last == null) {
 65             //当前尾结点last为null
 66             last = new Node(t, null);
 67             head.next = last;
 68         } else {
 69             //当前尾结点last不为null
 70             Node oldLast = last;
 71             last = new Node(t, null);
 72             oldLast.next = last;
 73         }
 74         //元素个数+1
 75         N++;
 76     }
 77 
 78     @Override
 79     public Iterator<T> iterator() {
 80         return new QIterator();
 81     }
 82 
 83     private class QIterator implements Iterator {
 84         private Node n;
 85 
 86         public QIterator() {
 87             this.n = head;
 88         }
 89 
 90         @Override
 91         public boolean hasNext() {
 92             return n.next != null;
 93         }
 94 
 95         @Override
 96         public Object next() {
 97             n = n.next;
 98             return n.item;
 99         }
100     }
101 
102 }

View Code

测试：

 1 package cn.itcast.algorithm.DemoTest.sortTest.linearTest;
 2 
 3 import cn.itcast.algorithm.Demo.linear.QueueDemo;
 4 
 5 public class QueueDemoTest {
 6 
 7     public static void main(String[] args) {
 8         //创建队列对象
 9         QueueDemo<String> q = new QueueDemo<>();
10 
11         //测试队列的enqueue方法
12         q.enqueue("a");
13         q.enqueue("b");
14         q.enqueue("c");
15         q.enqueue("d");
16 
17         for (String str : q) {
18             System.out.println(str);
19         }
20 
21         System.out.println("-------------------------------");
22         //测试队列的dequeue方法
23         String result = q.dequeue();
24         System.out.println("出队列的元素是："+result);
25         System.out.println("剩余的元素个数："+q.size());
26 
27     }
28 }

View Code

结果：

a
b
c
d
-------------------------------
出队列的元素是：a
剩余的元素个数：3