线性结构是包含n个相同类型元素的优先序列。在线性结构中，数据元素的前后关系是“一对一”的，即线性关系。
对于线性结构L=(a1, a2, ..., an)：
a.当1≤i<n且i<j≤n时，aj是ai的后继。ai+1是ai的直接后继。
b.当1<i≤n且1≤j<i时，aj是ai的前驱。ai-1是ai的直接前驱。
c.a1是头元素。头元素没有前驱。
d.an是尾元素。尾元素没有后继。
线性结构的存储表示主要有两种：
顺序存储：借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系。采用顺序存储的线性结构通常使用数组来存储相同类型的元素。
链式存储：借助指示数据元素存储地址的指针来表示元素之间的逻辑关系。采用链式存储的线性结构通常使用结点来存储元素，该结点中使用指针变量指向其直接前驱或直接后继的结点。
典型的线性结构有栈、队列和线性表等。
如果只允许在序列末端进行操作，这种线性结构称为栈。栈是一种后进先出的线性结构。
对于栈来说，尾元素所在端称为栈顶，头元素所在端称为栈底。不含任何元素的栈称为空栈。
栈的插入操作是将新元素压入栈顶，称为入栈；栈的删除操作是将栈顶元素删除，称为出栈。
可以将栈的操作定义成如下接口：
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 }
按存储结构分类，栈可以分为顺序栈和链栈。
采用顺序存储的栈称为顺序栈。顺序栈的定义如下：
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 }
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 }
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 }
按存储结构分类，队列可以分为顺序队列和链队列。
采用顺序存储的队列称为顺序队列。顺序队列的定义如下：
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 }
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 }
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 }
按存储结构分类，线性表可分为顺序表和链表。
采用顺序存储的线性表称为顺序表。顺序表的定义如下：
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 }
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 }
双向链表是结点有两个指针，一个指向直接后继结点，一个指向直接前驱结点的链表。双向链表的定义为：
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 }
单循环链表是尾元素的直接后继为头元素的单链表。
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 }
双向循环链表是尾元素的直接后继为头元素，头元素的直接前驱为尾元素的双向链表。
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 }
原文：https://www.cnblogs.com/lqkStudy/p/11291402.html
