概述
线性结构是包含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{ 2 3 /** 4 * 销毁栈 5 */ 6 void destroyStack(); 7 8 /** 9 * 判断栈是否为空10 * @return 若空则返回true，否则返回false11 */12 boolean stackEmpty();13 14 /**15 * 清空栈16 */17 void clearStack();18 19 /**20 * 元素压入栈21 * @param e22 */23 void push(E e);24 25 /**26 * 栈顶元素出栈27 * @return28 */29 E pop();30 31 /**32 * 取栈顶元素33 * @return34 */35 E getTop();36 37 /**38 * 栈内元素个数39 * @return40 */41 int stackLength();42 43 }
按存储结构分类，栈可以分为顺序栈和链栈。
顺序栈
采用顺序存储的栈称为顺序栈。顺序栈的定义如下：
1 import java.util.Arrays; 2 3 public class SqStackimplements Stack { 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 @Override102 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 LStackimplements Stack { 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 @Override30 public void destroyStack() {31 top = null;32 length = -1;33 }34 35 @Override36 public boolean stackEmpty() {37 if (length == -1) {38 throw new StackException("请先初始化！");39 }40 return length == 0;41 }42 43 @Override44 public void clearStack() {45 if (length == -1) {46 throw new StackException("请先初始化！");47 }48 top = null;49 length = 0;50 }51 52 @Override53 public void push(E e) {54 LSNode elem = new LSNode(e, top);55 top = elem;56 length++;57 }58 59 @Override60 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 @Override71 public E getTop() {72 if (stackEmpty()) {73 throw new StackException("栈内没有元素！");74 }75 return top.elem;76 }77 78 @Override79 public int stackLength() {80 if (length == -1) {81 throw new StackException("请先初始化！");82 }83 return length;84 }85 86 @SuppressWarnings("unchecked")87 @Override88 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{ 2 3 /** 4 * 销毁队列 5 */ 6 void destroyQueue(); 7 8 /** 9 * 清空队列10 */11 void clearQueue();12 13 /**14 * 判断队列是否为空队列15 * @return 若队列为空队列则返回true，否则返回false16 */17 boolean queueEmpty();18 19 /**20 * 返回队列中元素个数，即队列的长度21 * @return22 */23 int queueLength();24 25 /**26 * 若队列不空，则返回队列的头元素27 * @return28 */29 E getHead();30 31 /**32 * 在当前队列的尾元素之后插入元素作为新的尾元素33 * @param e34 */35 void enQueue(E e);36 37 /**38 * 若队列不空则删除当前队列中的头元素并返回该元素39 * @return40 */41 E deQueue();42 43 }
按存储结构分类，队列可以分为顺序队列和链队列。
顺序队列
采用顺序存储的队列称为顺序队列。顺序队列的定义如下：
1 import java.util.Arrays; 2 3 public class SqQueueimplements Queue { 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 @Override100 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 LQueueimplements Queue { 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 @Override102 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 @Override119 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{ 2 3 /** 4 * 销毁表 5 */ 6 void destroyList(); 7 8 /** 9 * 清空表10 */11 void clearList();12 13 /**14 * 判断表是否为空表15 * @return 表为空表则返回true，否则返回false16 */17 boolean listEmpty();18 19 /**20 * 返回表中元素个数21 * @return22 */23 int listLength();24 25 /**26 * 返回表中第i个元素27 * @param i28 * @return29 */30 E getElem(int i);31 32 /**33 * 在表中顺序查找元素34 * @param e35 * @return 成功时返回该元素在表中第一次出现的位置，否则返回-136 */37 int search(E e);38 39 /**40 * 遍历表41 */42 void listTraverse();43 44 /**45 * 为表中第i个元素赋值46 * @param i47 * @param e48 */49 void putElem(int i, E e);50 51 /**52 * 在表中第i个位置插入元素53 * @param i54 * @param e55 */56 void appendElem(int i, E e);57 58 /**59 * 删除表中第i个元素60 * @param i61 */62 E deleteElem(int i);63 64 }
按存储结构分类，线性表可分为顺序表和链表。
顺序表
采用顺序存储的线性表称为顺序表。顺序表的定义如下：
1 import java.util.Arrays; 2 3 public class SqListimplements List { 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 @Override103 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 @Override114 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 @Override138 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 LinkListimplements List { 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 @Override104 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 @Override120 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 @Override144 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 DuLinkListimplements List { 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 @Override101 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 @Override112 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 @Override137 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 CirLinkListimplements List { 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 @Override111 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 @Override127 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 @Override156 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 DuCirLinkListimplements List { 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 @Override108 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 @Override119 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 @Override149 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 }