线性结构

概述

　　线性结构是包含n个相同类型元素的优先序列。在线性结构中，数据元素的前后关系是“一对一”的，即线性关系。

　　对于线性结构L=(a₁, a₂, ..., a_n)：

　　　　a.当1≤i<n且i<j≤n时，a_j是a_i的后继。a_i+1是a_i的直接后继。

　　　　b.当1<i≤n且1≤j<i时，a_j是a_i的前驱。a_i-1是a_i的直接前驱。

　　　　c.a₁是头元素。头元素没有前驱。

　　　　d.a_n是尾元素。尾元素没有后继。

　　线性结构的存储表示主要有两种：

　　　　顺序存储：借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系。采用顺序存储的线性结构通常使用数组来存储相同类型的元素。

　　　　链式存储：借助指示数据元素存储地址的指针来表示元素之间的逻辑关系。采用链式存储的线性结构通常使用结点来存储元素，该结点中使用指针变量指向其直接前驱或直接后继的结点。

　　典型的线性结构有栈、队列和线性表等。

栈

　　如果只允许在序列末端进行操作，这种线性结构称为栈。栈是一种后进先出的线性结构。

　　对于栈来说，尾元素所在端称为栈顶，头元素所在端称为栈底。不含任何元素的栈称为空栈。

　　栈的插入操作是将新元素压入栈顶，称为入栈；栈的删除操作是将栈顶元素删除，称为出栈。

　　可以将栈的操作定义成如下接口：

 1 public interface Stack<E> {
 2 
 3     /**
 4      * 销毁栈
 5      */
 6     void destroyStack();
 7 
 8     /**
 9      * 判断栈是否为空
10      * @return  若空则返回true，否则返回false
11      */
12     boolean stackEmpty();
13 
14     /**
15      * 清空栈
16      */
17     void clearStack();
18 
19     /**
20      * 元素压入栈
21      * @param e
22      */
23     void push(E e);
24 
25     /**
26      * 栈顶元素出栈
27      * @return
28      */
29     E pop();
30 
31     /**
32      * 取栈顶元素
33      * @return
34      */
35     E getTop();
36 
37     /**
38      * 栈内元素个数
39      * @return
40      */
41     int stackLength();
42 
43 }

Stack

　　按存储结构分类，栈可以分为顺序栈和链栈。

顺序栈

　　采用顺序存储的栈称为顺序栈。顺序栈的定义如下：

  1 import java.util.Arrays;
  2 
  3 public class SqStack<E> implements Stack<E> {
  4 
  5     /**
  6      * 存储空间
  7      */
  8     private Object[] elem = null;
  9 
 10     /**
 11      * 栈顶位标
 12      */
 13     private int top = -1;
 14 
 15     /**
 16      * 当前分配的存储容量
 17      */
 18     private int size = -1;
 19 
 20     /**
 21      * 初始存储容量
 22      */
 23     private int initialSize = -1;
 24 
 25     /**
 26      * 扩容时，增加的存储容量
 27      */
 28     private int increment;
 29 
 30     public SqStack(int size, int inc) {
 31         elem = new Object[size];
 32         top = 0;
 33         initialSize = size;
 34         this.size = size;
 35         increment = inc;
 36     }
 37 
 38     @Override
 39     public void destroyStack() {
 40         elem = null;
 41         top = initialSize = size = increment = -1;
 42     }
 43 
 44     @Override
 45     public boolean stackEmpty() {
 46         if (elem == null) {
 47             throw new StackException("请先初始化！");
 48         }
 49         return top == 0;
 50     }
 51 
 52     @Override
 53     public void clearStack() {
 54         if (elem == null) {
 55             throw new StackException("请先初始化！");
 56         }
 57         elem = new Object[initialSize];
 58         top = 0;
 59         size = initialSize;
 60     }
 61 
 62     @Override
 63     public void push(E e) {
 64         if (elem == null) {
 65             throw new StackException("请先初始化！");
 66         }
 67         if (top >= size) {
 68             Object[] elem = new Object[size + increment];
 69             System.arraycopy(this.elem, 0, elem, 0, top);
 70             this.elem = elem;
 71             size += increment;
 72         }
 73         elem[top++] = e;
 74     }
 75 
 76     @SuppressWarnings("unchecked")
 77     @Override
 78     public E pop() {
 79         if (stackEmpty()) {
 80             throw new StackException("栈内没有元素！");
 81         }
 82         E e = (E) elem[--top];
 83         elem[top] = null;
 84         return e;
 85     }
 86 
 87     @SuppressWarnings("unchecked")
 88     @Override
 89     public E getTop() {
 90         if (stackEmpty()) {
 91             throw new StackException("栈内没有元素！");
 92         }
 93         return (E) elem[top - 1];
 94     }
 95 
 96     @Override
 97     public int stackLength() {
 98         return top;
 99     }
100 
101     @Override
102     public String toString() {
103         if (stackEmpty()) {
104             throw new StackException("栈内没有元素！");
105         }
106         Object[] elem = new Object[top];
107         System.arraycopy(this.elem, 0, elem, 0, top);
108         return "" + Arrays.asList(elem);
109     }
110 
111 }

SqStack

　　a.使用泛型来控制入栈的元素类型，保证数组中的元素类型一致。

　　b.采用Object数组来存储元素。

　　c.top为栈顶位标，也可以表示栈中元素的个数。

　　d.size是栈当前的容量。当top == size，即栈中元素个数为栈当前容量时，表示栈已满。

　　e.increment是扩容的增量，元素入栈前判断栈是否已满，已满则扩容。

链栈

　　采用链式存储的栈称为链栈。链栈的定义如下：

 1 import java.util.Arrays;
 2 
 3 public class LStack<E> implements Stack<E> {
 4 
 5     private class LSNode {
 6         private E elem;
 7         private LSNode prior;
 8 
 9         private LSNode(E elem, LSNode prior) {
10             this.elem = elem;
11             this.prior = prior;
12         }
13     }
14 
15     /**
16      * 栈顶元素
17      */
18     private LSNode top = null;
19 
20     /**
21      * 栈内元素个数
22      */
23     private int length = -1;
24 
25     public LStack() {
26         length = 0;
27     }
28 
29     @Override
30     public void destroyStack() {
31         top = null;
32         length = -1;
33     }
34 
35     @Override
36     public boolean stackEmpty() {
37         if (length == -1) {
38             throw new StackException("请先初始化！");
39         }
40         return length == 0;
41     }
42 
43     @Override
44     public void clearStack() {
45         if (length == -1) {
46             throw new StackException("请先初始化！");
47         }
48         top = null;
49         length = 0;
50     }
51 
52     @Override
53     public void push(E e) {
54         LSNode elem = new LSNode(e, top);
55         top = elem;
56         length++;
57     }
58 
59     @Override
60     public E pop() {
61         if (stackEmpty()) {
62             throw new StackException("栈内没有元素！");
63         }
64         E e = top.elem;
65         top = top.prior;
66         length--;
67         return e;
68     }
69 
70     @Override
71     public E getTop() {
72         if (stackEmpty()) {
73             throw new StackException("栈内没有元素！");
74         }
75         return top.elem;
76     }
77 
78     @Override
79     public int stackLength() {
80         if (length == -1) {
81             throw new StackException("请先初始化！");
82         }
83         return length;
84     }
85 
86     @SuppressWarnings("unchecked")
87     @Override
88     public String toString() {
89         Object[] elems = new Object[length];
90         elems[length - 1] = top;
91         for (int i = length - 2; i >= 0; i--) {
92             elems[i] = ((LSNode) elems[i + 1]).prior;
93         }
94         return "" + Arrays.asList(elems);
95     }
96 
97 }

LStack

　　a.使用泛型来控制入栈的元素类型，保证每一个结点的数据类型一致。

　　b.采用LSNode来表示结点，其中除了数据之外还有一个prior指针指向其直接前驱的结点。

　　c.top存储了栈顶结点。

　　d.length表示元素个数。

队列

　　如果只允许在序列两端进行操作，这种线性结构称为队列。队列是一种先进先出的线性结构。

　　对于队列来说，头元素所在端称为队头，尾元素所在端称为队尾。不含任何元素的队列称为空队列。

　　队列的插入操作是将新元素插入队尾，称为入队；队列的删除操作是将队头元素删除，称为出队。

　　可以将队列的操作定义成如下接口：

 1 public interface Queue<E> {
 2 
 3     /**
 4      * 销毁队列
 5      */
 6     void destroyQueue();
 7 
 8     /**
 9      * 清空队列
10      */
11     void clearQueue();
12 
13     /**
14      * 判断队列是否为空队列
15      * @return  若队列为空队列则返回true，否则返回false
16      */
17     boolean queueEmpty();
18 
19     /**
20      * 返回队列中元素个数，即队列的长度
21      * @return
22      */
23     int queueLength();
24 
25     /**
26      * 若队列不空，则返回队列的头元素
27      * @return
28      */
29     E getHead();
30 
31     /**
32      * 在当前队列的尾元素之后插入元素作为新的尾元素
33      * @param e
34      */
35     void enQueue(E e);
36 
37     /**
38      * 若队列不空则删除当前队列中的头元素并返回该元素
39      * @return
40      */
41     E deQueue();
42 
43 }

Queue

　　按存储结构分类，队列可以分为顺序队列和链队列。

顺序队列

　　采用顺序存储的队列称为顺序队列。顺序队列的定义如下：

  1 import java.util.Arrays;
  2 
  3 public class SqQueue<E> implements Queue<E> {
  4 
  5     /**
  6      * 存储空间
  7      */
  8     private Object[] elem = null;
  9 
 10     /**
 11      * 队头位标
 12      */
 13     private int front = -1;
 14 
 15     /**
 16      * 队尾位标，指示队尾元素的下一位置
 17      */
 18     private int rear = -1;
 19 
 20     /**
 21      * 存储容量
 22      */
 23     private int maxSize = -1;
 24 
 25     public SqQueue(int size) {
 26         elem = new Object[size];
 27         front = rear = 0;
 28         maxSize = size;
 29     }
 30 
 31     @Override
 32     public void destroyQueue() {
 33         elem = null;
 34         front = rear = maxSize = -1;
 35     }
 36 
 37     @Override
 38     public void clearQueue() {
 39         if (elem == null) {
 40             throw new QueueException("请先初始化！");
 41         }
 42         elem = new Object[maxSize];
 43         front = rear = 0;
 44     }
 45 
 46     @Override
 47     public boolean queueEmpty() {
 48         if (elem == null) {
 49             throw new QueueException("请先初始化！");
 50         }
 51         return elem[front] == null;
 52     }
 53 
 54     @Override
 55     public int queueLength() {
 56         if (elem == null) {
 57             throw new QueueException("请先初始化！");
 58         }
 59         if (front == rear) {
 60             if (elem[front] == null) {
 61                 return 0;
 62             } else {
 63                 return maxSize;
 64             }
 65         }
 66         return front > rear ? rear + maxSize - front : rear  - front;
 67     }
 68 
 69     @SuppressWarnings("unchecked")
 70     @Override
 71     public E getHead() {
 72         if (queueEmpty()) {
 73             throw new QueueException("队列中没有元素！");
 74         }
 75         return (E) elem[front];
 76     }
 77 
 78     @Override
 79     public void enQueue(E e) {
 80         if (elem == null) {
 81             throw new QueueException("请先初始化！");
 82         }
 83         if (elem[rear] != null) {
 84             throw new QueueException("队列已满！");
 85         }
 86         elem[rear] = e;
 87         rear = (rear + 1) % maxSize;
 88     }
 89 
 90     @SuppressWarnings("unchecked")
 91     @Override
 92     public E deQueue() {
 93         E e = (E) elem[front];
 94         elem[front] = null;
 95         front = (front + 1) % maxSize;
 96         return e;
 97     }
 98 
 99     @Override
100     public String toString() {
101         int len = queueLength();
102         Object[] elem = new Object[len];
103         for (int i = 0, j = front; i < len; i++, j = (j + 1) % maxSize) {
104             elem[i] = this.elem[j];
105         }
106         return "" + Arrays.asList(elem);
107     }
108 
109 }

SqQueue

　　a.使用泛型来控制入队的元素类型，保证数组中的元素类型一致。

　　b.front和rear分别为队头和队尾位标。

　　c.maxSize为队列的容量。

　　d.新元素入队，rear循环加1；头元素出队，front循环加1。

　　e.front指向的位置没有元素，则队列为空；rear指向的位置有元素，则队列已满。

链队列

　　采用链式存储的队列称为链队列。链队列的定义如下：

  1 import java.util.Arrays;
  2 
  3 public class LQueue<E> implements Queue<E> {
  4 
  5     private class LQNode {
  6         private E elem;
  7         private LQNode next;
  8 
  9         private LQNode(E elem, LQNode next) {
 10             this.elem = elem;
 11             this.next = next;
 12         }
 13     }
 14 
 15     /**
 16      * 队头指针
 17      */
 18     private LQNode front = null;
 19 
 20     /**
 21      * 队尾指针
 22      */
 23     private LQNode rear = null;
 24 
 25     /**
 26      * 队列中元素个数
 27      */
 28     private int length = -1;
 29 
 30     /**
 31      * 类型
 32      * 带头结点（true）、不带头结点（false）
 33      */
 34     private boolean type;
 35 
 36     public LQueue(boolean type) {
 37         if (type) {
 38             front = rear = new LQNode(null, null);
 39         }
 40         length = 0;
 41         this.type = type;
 42     }
 43 
 44     @Override
 45     public void destroyQueue() {
 46         front = rear = null;
 47         length = -1;
 48     }
 49 
 50     @Override
 51     public void clearQueue() {
 52         if (length == -1) {
 53             throw new QueueException("请先初始化！");
 54         }
 55         if (type) {
 56             front = rear = new LQNode(null, null);
 57         } else {
 58             front = rear = null;
 59         }
 60         length = 0;
 61     }
 62 
 63     @Override
 64     public boolean queueEmpty() {
 65         if (length == -1) {
 66             throw new QueueException("请先初始化！");
 67         }
 68         return length == 0;
 69     }
 70 
 71     @Override
 72     public int queueLength() {
 73         if (length == -1) {
 74             throw new QueueException("请先初始化！");
 75         }
 76         return length;
 77     }
 78 
 79     @Override
 80     public E getHead() {
 81         if (queueEmpty()) {
 82             throw new QueueException("队列中没有元素！");
 83         }
 84         return type ? front.next.elem : front.elem;
 85     }
 86 
 87     @Override
 88     public void enQueue(E e) {
 89         if (length == -1) {
 90             throw new QueueException("请先初始化！");
 91         }
 92         if (length == 0 && ! type) {
 93             front = rear = new LQNode(e, null);
 94         } else {
 95             rear.next = new LQNode(e, null);
 96             rear = rear.next;
 97         }
 98         length++;
 99     }
100 
101     @Override
102     public E deQueue() {
103         if (queueEmpty()) {
104             throw new QueueException("队列中没有元素！");
105         }
106         E e;
107         if (type) {
108             e = front.next.elem;
109             front.next = front.next.next;
110         } else {
111             e = front.elem;
112             front = front.next;
113         }
114         length--;
115         return e;
116     }
117 
118     @Override
119     public String toString() {
120         Object[] elem = new Object[length];
121         LQNode node = type ? front.next : front;
122         for (int i = 0; i < length; i++, node = node.next) {
123             elem[i] = node.elem;
124         }
125         return "" + Arrays.asList(elem);
126     }
127 
128 }

LQueue

　　a.使用泛型来控制入队的元素类型，保证每一个结点的数据类型一致。

　　b.采用LQNode来表示结点，其中除了数据之外还有一个next指针指向其直接后继的结点。

　　c.front和rear分别为队头和队尾结点。

　　d.length表示队中元素个数。

　　e.type区分该队列是否带头结点。链队列又分为带头结点和不带头结点两种。头结点是一个空结点，带头结点指front指向该头结点，其next指针指向队列头元素的结点；不带头结点指front指向队列头元素的结点。

线性表

　　如果允许在序列任意位置进行操作，这种线性结构称为线性表。

　　线性表中所含元素的个数称为线性表的长度，长度为0的线性表称为空表。

　　线性表允许在任意位置插入、删除，以及查询和修改任意位置的元素等。

　　可以将线性表的操作定义成如下接口：

 1 public interface List<E> {
 2 
 3     /**
 4      * 销毁表
 5      */
 6     void destroyList();
 7 
 8     /**
 9      * 清空表
10      */
11     void clearList();
12 
13     /**
14      * 判断表是否为空表
15      * @return  表为空表则返回true，否则返回false
16      */
17     boolean listEmpty();
18 
19     /**
20      * 返回表中元素个数
21      * @return
22      */
23     int listLength();
24 
25     /**
26      * 返回表中第i个元素
27      * @param i
28      * @return
29      */
30     E getElem(int i);
31 
32     /**
33      * 在表中顺序查找元素
34      * @param e
35      * @return  成功时返回该元素在表中第一次出现的位置，否则返回-1
36      */
37     int search(E e);
38 
39     /**
40      * 遍历表
41      */
42     void listTraverse();
43 
44     /**
45      * 为表中第i个元素赋值
46      * @param i
47      * @param e
48      */
49     void putElem(int i, E e);
50 
51     /**
52      * 在表中第i个位置插入元素
53      * @param i
54      * @param e
55      */
56     void appendElem(int i, E e);
57 
58     /**
59      * 删除表中第i个元素
60      * @param i
61      */
62     E deleteElem(int i);
63 
64 }

List

　　按存储结构分类，线性表可分为顺序表和链表。

顺序表

　　采用顺序存储的线性表称为顺序表。顺序表的定义如下：

  1 import java.util.Arrays;
  2 
  3 public class SqList<E> implements List<E> {
  4 
  5     /**
  6      * 存储空间
  7      */
  8     private Object[] elem = null;
  9 
 10     /**
 11      * 当前长度
 12      */
 13     private int length = -1;
 14 
 15     /**
 16      * 初始存储容量
 17      */
 18     private int initialSize = -1;
 19 
 20     /**
 21      * 存储容量
 22      */
 23     private int size = -1;
 24 
 25     /**
 26      * 扩容的增量
 27      */
 28     private int increment = -1;
 29 
 30     public SqList(int size, int inc) {
 31         elem = new Object[size];
 32         length = 0;
 33         initialSize = size;
 34         this.size = size;
 35         increment = inc;
 36     }
 37 
 38     @Override
 39     public void destroyList() {
 40         elem = null;
 41         length = initialSize = size = increment = -1;
 42     }
 43 
 44     @Override
 45     public void clearList() {
 46         elem = new Object[initialSize];
 47         length = 0;
 48         size = initialSize;
 49     }
 50 
 51     @Override
 52     public boolean listEmpty() {
 53         if (elem == null) {
 54             throw new ListException("请先初始化！");
 55         }
 56         return length == 0;
 57     }
 58 
 59     @Override
 60     public int listLength() {
 61         if (elem == null) {
 62             throw new ListException("请先初始化！");
 63         }
 64         return length;
 65     }
 66 
 67     @SuppressWarnings("unchecked")
 68     @Override
 69     public E getElem(int i) {
 70         if (listEmpty()) {
 71             throw new ListException("表中没有元素！");
 72         }
 73         if (i < 0 || i >= length) {
 74             throw new ListException("位标不在范围内！");
 75         }
 76         return (E) elem[i];
 77     }
 78 
 79     @Override
 80     public int search(E e) {
 81         if (listEmpty()) {
 82             throw new ListException("表中没有元素！");
 83         }
 84         for (int i = 0; i < length; i++) {
 85             if (e.equals(elem[i])) {
 86                 return i;
 87             }
 88         }
 89         return -1;
 90     }
 91 
 92     @Override
 93     public void listTraverse() {
 94         if (listEmpty()) {
 95             throw new ListException("表中没有元素！");
 96         }
 97         Object[] elem = new Object[length];
 98         System.arraycopy(this.elem, 0, elem, 0, length);
 99         System.out.println(Arrays.asList(elem));
100     }
101 
102     @Override
103     public void putElem(int i, E e) {
104         if (listEmpty()) {
105             throw new ListException("表中没有元素！");
106         }
107         if (i < 0 || i >= length) {
108             throw new ListException("位标不在范围内！");
109         }
110         elem[i] = e;
111     }
112 
113     @Override
114     public void appendElem(int i, E e) {
115         if (elem == null) {
116             throw new ListException("请先初始化！");
117         }
118         if (i < 0) {
119             throw new ListException("位标不能为负数！");
120         }
121         if (length >= size) {
122             size += increment;
123             Object[] elem = new Object[size];
124             System.arraycopy(this.elem, 0, elem, 0, length);
125             this.elem = elem;
126         }
127         if (i >= length) {
128             i = length;
129         } else {
130             System.arraycopy(elem, i, elem, i + 1, length - i);
131         }
132         elem[i] = e;
133         length++;
134     }
135 
136     @SuppressWarnings("unchecked")
137     @Override
138     public E deleteElem(int i) {
139         if (listEmpty()) {
140             throw new ListException("表中没有元素！");
141         }
142         if (i < 0) {
143             throw new ListException("位标不能为负数！");
144         }
145         if (i >= length - 1) {
146             i = length - 1;
147         }
148         E e = (E) elem[i];
149         if (i < length - 1) {
150             System.arraycopy(elem, i + 1, elem, i, length - 1 - i);
151         }
152         elem[--length] = null;
153         return e;
154     }
155 
156 }

SqList

　　a.使用泛型来控制插入的元素类型，保证数组中的元素类型一致。

　　b.采用Object数组来存储元素。

　　c.length表示栈中元素的个数。

　　d.size是栈当前的容量。当length == size，即栈中元素个数为栈当前容量时，表示栈已满。

　　e.increment是扩容的增量，元素入栈前判断栈是否已满，已满则扩容。

　　f.位标i必须是[0, length - 1)的范围内。

链表

　　采用链式存储的线性表称为链表。链表分为以下几类：

单链表

　　单链表是结点只有一个指向直接后继结点的指针的链表。单链表的定义为：

  1 import java.util.Arrays;
  2 
  3 public class LinkList<E> implements List<E> {
  4 
  5     private class LNode {
  6         E elem;
  7         LNode next;
  8 
  9         private LNode(E elem, LNode next) {
 10             this.elem = elem;
 11             this.next = next;
 12         }
 13     }
 14 
 15     /**
 16      * 头结点
 17      */
 18     private LNode head = null;
 19 
 20     /**
 21      * 当前长度
 22      */
 23     private int length = -1;
 24 
 25     public LinkList() {
 26         length = 0;
 27     }
 28 
 29     @Override
 30     public void destroyList() {
 31         head = null;
 32         length = -1;
 33     }
 34 
 35     @Override
 36     public void clearList() {
 37         if (length == -1) {
 38             throw new ListException("请先初始化！");
 39         }
 40         head = null;
 41         length = 0;
 42     }
 43 
 44     @Override
 45     public boolean listEmpty() {
 46         if (length == -1) {
 47             throw new ListException("请先初始化！");
 48         }
 49         return length == 0;
 50     }
 51 
 52     @Override
 53     public int listLength() {
 54         if (length == -1) {
 55             throw new ListException("请先初始化！");
 56         }
 57         return length;
 58     }
 59 
 60     @Override
 61     public E getElem(int i) {
 62         if (listEmpty()) {
 63             throw new ListException("表中没有元素！");
 64         }
 65         if (i < 0 || i >= length) {
 66             throw new ListException("位标不在范围内！");
 67         }
 68         LNode node = head;
 69         while (i > 0) {
 70             node = node.next;
 71             i--;
 72         }
 73         return node.elem;
 74     }
 75 
 76     @Override
 77     public int search(E e) {
 78         if (listEmpty()) {
 79             throw new ListException("表中没有元素！");
 80         }
 81         LNode node = head;
 82         for (int i = 0; i < length; i++, node = node.next) {
 83             if (e.equals(node.elem)) {
 84                 return i;
 85             }
 86         }
 87         return -1;
 88     }
 89 
 90     @Override
 91     public void listTraverse() {
 92         if (listEmpty()) {
 93             throw new ListException("表中没有元素！");
 94         }
 95         Object[] elem = new Object[length];
 96         LNode node = head;
 97         for (int i = 0; i < length; i++, node = node.next) {
 98             elem[i] = node.elem;
 99         }
100         System.out.println(Arrays.asList(elem));
101     }
102 
103     @Override
104     public void putElem(int i, E e) {
105         if (listEmpty()) {
106             throw new ListException("表中没有元素！");
107         }
108         if (i < 0 || i >= length) {
109             throw new ListException("位标不在范围内！");
110         }
111         LNode node = head;
112         while (i > 0) {
113             node = node.next;
114             i--;
115         }
116         node.elem = e;
117     }
118 
119     @Override
120     public void appendElem(int i, E e) {
121         if (length == -1) {
122             throw new ListException("请先初始化！");
123         }
124         if (i < 0) {
125             throw new ListException("位标不能为负数！");
126         }
127         if (length == 0 || i == 0) {
128             head = new LNode(e, head);
129         } else {
130             if (i > length) {
131                 i = length;
132             }
133             LNode node = head;
134             while (i > 1) {
135                 node = node.next;
136                 i--;
137             }
138             node.next = new LNode(e, node.next);
139         }
140         length++;
141     }
142 
143     @Override
144     public E deleteElem(int i) {
145         if (listEmpty()) {
146             throw new ListException("表中没有元素！");
147         }
148         if (i < 0) {
149             throw new ListException("位标不能为负数！");
150         }
151         E e;
152         if (i == 0) {
153             e = head.elem;
154             head = head.next;
155         } else {
156             if (i >= length - 1) {
157                 i = length - 1;
158             }
159             LNode node = head;
160             while (i > 1) {
161                 node = node.next;
162                 i--;
163             }
164             e = node.next.elem;
165             node.next = node.next.next;
166         }
167         length--;
168         return e;
169     }
170 
171 }

LinkList

双向链表

　　双向链表是结点有两个指针，一个指向直接后继结点，一个指向直接前驱结点的链表。双向链表的定义为：

  1 import java.util.Arrays;
  2 
  3 public class DuLinkList<E> implements List<E> {
  4 
  5     private class DuLNode {
  6         E elem;
  7         DuLNode prior;
  8         DuLNode next;
  9 
 10         private DuLNode(E elem, DuLNode prior, DuLNode next) {
 11             this.elem = elem;
 12             this.prior = prior;
 13             this.next = next;
 14         }
 15     }
 16 
 17     /**
 18      * 头结点
 19      */
 20     private DuLNode head = null;
 21 
 22     /**
 23      * 当前长度
 24      */
 25     private int length = -1;
 26 
 27     public DuLinkList() {
 28         length = 0;
 29     }
 30 
 31     @Override
 32     public void destroyList() {
 33         head = null;
 34         length = -1;
 35     }
 36 
 37     @Override
 38     public void clearList() {
 39         if (length == -1) {
 40             throw new ListException("请先初始化！");
 41         }
 42         head = null;
 43         length = 0;
 44     }
 45 
 46     @Override
 47     public boolean listEmpty() {
 48         if (length == -1) {
 49             throw new ListException("请先初始化！");
 50         }
 51         return length == 0;
 52     }
 53 
 54     @Override
 55     public int listLength() {
 56         if (length == -1) {
 57             throw new ListException("请先初始化！");
 58         }
 59         return length;
 60     }
 61 
 62     @Override
 63     public E getElem(int i) {
 64         if (listEmpty()) {
 65             throw new ListException("表中没有元素！");
 66         }
 67         if (i < 0 || i >= length) {
 68             throw new ListException("位标不在范围内！");
 69         }
 70         return get(i).elem;
 71     }
 72 
 73     @Override
 74     public int search(E e) {
 75         if (listEmpty()) {
 76             throw new ListException("表中没有元素！");
 77         }
 78         DuLNode node = head;
 79         for (int i = 0; i < length; i++, node = node.next) {
 80             if (e.equals(node.elem)) {
 81                 return i;
 82             }
 83         }
 84         return -1;
 85     }
 86 
 87     @Override
 88     public void listTraverse() {
 89         if (listEmpty()) {
 90             throw new ListException("表中没有元素！");
 91         }
 92         Object[] elem = new Object[length];
 93         DuLNode node = head;
 94         for (int i = 0; i < length; i++, node = node.next) {
 95             elem[i] = node.elem;
 96         }
 97         System.out.println(Arrays.asList(elem));
 98     }
 99 
100     @Override
101     public void putElem(int i, E e) {
102         if (listEmpty()) {
103             throw new ListException("表中没有元素！");
104         }
105         if (i < 0 || i >= length) {
106             throw new ListException("位标不在范围内！");
107         }
108         get(i).elem = e;
109     }
110 
111     @Override
112     public void appendElem(int i, E e) {
113         if (i < 0) {
114             throw new ListException("位标不能为负数！");
115         }
116         if (listEmpty()) {
117             head = new DuLNode(e, null, head);
118         } else if (i == 0) {
119             DuLNode node = new DuLNode(e, null, head);
120             head.prior = node;
121             head = node;
122         } else if (i >= length) {
123             DuLNode prior = get(length - 1);
124             DuLNode node = new DuLNode(e, prior, null);
125             prior.next = node;
126         } else {
127             DuLNode next = get(i);
128             DuLNode prior = next.prior;
129             DuLNode node = new DuLNode(e, prior, next);
130             next.prior = node;
131             prior.next = node;
132         }
133         length++;
134     }
135 
136     @Override
137     public E deleteElem(int i) {
138         if (listEmpty()) {
139             throw new ListException("表中没有元素！");
140         }
141         if (i < 0) {
142             throw new ListException("位标不能为负数！");
143         }
144         DuLNode node;
145         if (i == 0) {
146             node = head;
147             head = head.next;
148             head.prior = null;
149         } else if (i >= length - 1) {
150             node = get(length - 1);
151             node.prior.next = null;
152         } else {
153             node = get(i);
154             node.prior.next = node.next;
155             node.next.prior = node.prior;
156         }
157         length--;
158         return node.elem;
159     }
160 
161     private DuLNode get(int i) {
162         DuLNode node = head;
163         while (i > 0) {
164             node = node.next;
165             i--;
166         }
167         return node;
168     }
169 
170 }

DuLinkList

单循环链表

　　单循环链表是尾元素的直接后继为头元素的单链表。

  1 import java.util.Arrays;
  2 
  3 public class CirLinkList<E> implements List<E> {
  4 
  5     private class LNode {
  6         E elem;
  7         LNode next;
  8 
  9         private LNode(E elem, LNode next) {
 10             this.elem = elem;
 11             this.next = next;
 12         }
 13     }
 14 
 15     /**
 16      * 头结点
 17      */
 18     private LNode head = null;
 19 
 20     /**
 21      * 尾结点
 22      */
 23     private LNode tail = null;
 24 
 25     /**
 26      * 当前长度
 27      */
 28     private int length = -1;
 29 
 30     public CirLinkList() {
 31         length = 0;
 32     }
 33 
 34     @Override
 35     public void destroyList() {
 36         head = null;
 37         tail = null;
 38         length = -1;
 39     }
 40 
 41     @Override
 42     public void clearList() {
 43         if (length == -1) {
 44             throw new ListException("请先初始化！");
 45         }
 46         head = null;
 47         tail = null;
 48         length = 0;
 49     }
 50 
 51     @Override
 52     public boolean listEmpty() {
 53         if (length == -1) {
 54             throw new ListException("请先初始化！");
 55         }
 56         return length == 0;
 57     }
 58 
 59     @Override
 60     public int listLength() {
 61         if (length == -1) {
 62             throw new ListException("请先初始化！");
 63         }
 64         return length;
 65     }
 66 
 67     @Override
 68     public E getElem(int i) {
 69         if (listEmpty()) {
 70             throw new ListException("表中没有元素！");
 71         }
 72         if (i < 0 || i >= length) {
 73             throw new ListException("位标不在范围内！");
 74         }
 75         LNode node = head;
 76         while (i > 0) {
 77             node = node.next;
 78             i--;
 79         }
 80         return node.elem;
 81     }
 82 
 83     @Override
 84     public int search(E e) {
 85         if (listEmpty()) {
 86             throw new ListException("表中没有元素！");
 87         }
 88         LNode node = head;
 89         for (int i = 0; i < length; i++, node = node.next) {
 90             if (e.equals(node.elem)) {
 91                 return i;
 92             }
 93         }
 94         return -1;
 95     }
 96 
 97     @Override
 98     public void listTraverse() {
 99         if (listEmpty()) {
100             throw new ListException("表中没有元素！");
101         }
102         Object[] elem = new Object[length];
103         LNode node = head;
104         for (int i = 0; i < length; i++, node = node.next) {
105             elem[i] = node.elem;
106         }
107         System.out.println(Arrays.asList(elem));
108     }
109 
110     @Override
111     public void putElem(int i, E e) {
112         if (listEmpty()) {
113             throw new ListException("表中没有元素！");
114         }
115         if (i < 0 || i >= length) {
116             throw new ListException("位标不在范围内！");
117         }
118         LNode node = head;
119         while (i > 0) {
120             node = node.next;
121             i--;
122         }
123         node.elem = e;
124     }
125 
126     @Override
127     public void appendElem(int i, E e) {
128         if (length == -1) {
129             throw new ListException("请先初始化！");
130         }
131         if (i < 0) {
132             throw new ListException("位标不能为负数！");
133         }
134         if (length == 0) {
135             head = new LNode(e, null);
136             head.next = head;
137             tail = head;
138         } else if (i == 0) {
139             head = new LNode(e, head);
140             tail.next = head;
141         } else if (i >= length) {
142             tail.next = new LNode(e, head);
143             tail = tail.next;
144         } else {
145             LNode node = head;
146             while (i > 1) {
147                 node = node.next;
148                 i--;
149             }
150             node.next = new LNode(e, node.next);
151         }
152         length++;
153     }
154 
155     @Override
156     public E deleteElem(int i) {
157         if (listEmpty()) {
158             throw new ListException("表中没有元素！");
159         }
160         if (i < 0) {
161             throw new ListException("位标不能为负数！");
162         }
163         E e;
164         if (i == 0) {
165             e = head.elem;
166             head = head.next;
167             tail.next = head;
168         } else if (i >= length - 1) {
169             LNode node = head;
170             while (i > 1) {
171                 node = node.next;
172                 i--;
173             }
174             e = node.next.elem;
175             node.next = head;
176             tail = node;
177         } else {
178             LNode node = head;
179             while (i > 1) {
180                 node = node.next;
181                 i--;
182             }
183             e = node.next.elem;
184             node.next = node.next.next;
185         }
186         length--;
187         return e;
188     }
189 
190 }

CirLinkList

双向循环链表

　　双向循环链表是尾元素的直接后继为头元素，头元素的直接前驱为尾元素的双向链表。

  1 import java.util.Arrays;
  2 
  3 public class DuCirLinkList<E> implements List<E> {
  4 
  5     private class DuLNode {
  6         E elem;
  7         DuLNode prior;
  8         DuLNode next;
  9 
 10         private DuLNode(E elem, DuLNode prior, DuLNode next) {
 11             this.elem = elem;
 12             this.prior = prior;
 13             this.next = next;
 14         }
 15     }
 16 
 17     /**
 18      * 头结点
 19      */
 20     private DuLNode head = null;
 21 
 22     /**
 23      * 尾结点
 24      */
 25     private DuLNode tail = null;
 26 
 27     /**
 28      * 当前长度
 29      */
 30     private int length = -1;
 31 
 32     public DuCirLinkList() {
 33         length = 0;
 34     }
 35 
 36     @Override
 37     public void destroyList() {
 38         head = null;
 39         tail = null;
 40         length = -1;
 41     }
 42 
 43     @Override
 44     public void clearList() {
 45         if (length == -1) {
 46             throw new ListException("请先初始化！");
 47         }
 48         head = null;
 49         tail = null;
 50         length = 0;
 51     }
 52 
 53     @Override
 54     public boolean listEmpty() {
 55         if (length == -1) {
 56             throw new ListException("请先初始化！");
 57         }
 58         return length == 0;
 59     }
 60 
 61     @Override
 62     public int listLength() {
 63         if (length == -1) {
 64             throw new ListException("请先初始化！");
 65         }
 66         return length;
 67     }
 68 
 69     @Override
 70     public E getElem(int i) {
 71         if (listEmpty()) {
 72             throw new ListException("表中没有元素！");
 73         }
 74         if (i < 0 || i >= length) {
 75             throw new ListException("位标不在范围内！");
 76         }
 77         return get(i).elem;
 78     }
 79 
 80     @Override
 81     public int search(E e) {
 82         if (listEmpty()) {
 83             throw new ListException("表中没有元素！");
 84         }
 85         DuLNode node = head;
 86         for (int i = 0; i < length; i++, node = node.next) {
 87             if (e.equals(node.elem)) {
 88                 return i;
 89             }
 90         }
 91         return -1;
 92     }
 93 
 94     @Override
 95     public void listTraverse() {
 96         if (listEmpty()) {
 97             throw new ListException("表中没有元素！");
 98         }
 99         Object[] elem = new Object[length];
100         DuLNode node = head;
101         for (int i = 0; i < length; i++, node = node.next) {
102             elem[i] = node.elem;
103         }
104         System.out.println(Arrays.asList(elem));
105     }
106 
107     @Override
108     public void putElem(int i, E e) {
109         if (listEmpty()) {
110             throw new ListException("表中没有元素！");
111         }
112         if (i < 0 || i >= length) {
113             throw new ListException("位标不在范围内！");
114         }
115         get(i).elem = e;
116     }
117 
118     @Override
119     public void appendElem(int i, E e) {
120         if (i < 0) {
121             throw new ListException("位标不能为负数！");
122         }
123         if (listEmpty()) {
124             head = new DuLNode(e, null, null);
125             tail = head;
126             head.prior = head;
127             head.next = head;
128         } else if (i == 0) {
129             DuLNode node = new DuLNode(e, tail, head);
130             head.prior = node;
131             tail.next = node;
132             head = node;
133         } else if (i >= length) {
134             DuLNode node = new DuLNode(e, tail, head);
135             tail.next = node;
136             head.prior = node;
137             tail = node;
138         } else {
139             DuLNode next = get(i);
140             DuLNode prior = next.prior;
141             DuLNode node = new DuLNode(e, prior, next);
142             next.prior = node;
143             prior.next = node;
144         }
145         length++;
146     }
147 
148     @Override
149     public E deleteElem(int i) {
150         if (listEmpty()) {
151             throw new ListException("表中没有元素！");
152         }
153         if (i < 0) {
154             throw new ListException("位标不能为负数！");
155         }
156         DuLNode node;
157         if (i == 0) {
158             node = head;
159             head = head.next;
160             head.prior = tail;
161             tail.next = head;
162         } else if (i >= length - 1) {
163             node = tail;
164             tail = tail.prior;
165             tail.next = head;
166             head.prior = tail;
167         } else {
168             node = get(i);
169             node.prior.next = node.next;
170             node.next.prior = node.prior;
171         }
172         length--;
173         return node.elem;
174     }
175 
176     private DuLNode get(int i) {
177         DuLNode node = head;
178         while (i > 0) {
179             node = node.next;
180             i--;
181         }
182         return node;
183     }
184 
185 }

DuCirLinkList