1.链表简介

单向链表的数据结构如下图所示

2. 代码实现链表

package LinkedLidt01; public class LinkedList<E> { private class Node { public E e; public Node next; public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e, null); } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node dummyHead; int size; /** * 构造函数 */ public LinkedList() { dummyHead = new Node(null, null); size = 0; } public int getSize() { return size; } /** * 判断是否为空 * * @return */ public boolean isEmpty() { return size == 0; } /** * 向索引位置添加元素 * * @param index * @param e */ public void add(int index, E e) { if (index < 0 || index > size) throw new IllegalArgumentException("Add failed. Illegall index"); Node pre = dummyHead; //前一个结点 for (int i = 0; i < index; i++) { pre = pre.next; } pre.next = new Node(e, pre.next); size++; } /** * 向链表首添加元素 * @param e */ public void addFirst(E e) { add(0,e); } public void addLast(E e) { add(size, e); } /** * 获取索引为index的元素 * @param index * @return */ public E get(int index){ if (index < 0 ||index >= size){ throw new IllegalArgumentException("Get failed.Illegal index"); } Node cur = dummyHead.next; // 当前节点 for (int i = 0; i < index; i++) { cur = cur.next; } return cur.e; } /** * 获取链表第一个元素 */ public E getFirst(){ return get(0); } /** * 获取最后一个元素 * @return */ public E getLast(){ return get(size); } /** * 修改链表中第index个位置的元素为e * @param index * @param e */ public void set(int index,E e){ if (index < 0 || index >= size) { throw new IllegalArgumentException("Set failed.Illegal index"); } Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } cur.e = e; } /** * 判断是否含有元素e * @param e * @return */ public boolean contains(E e){ Node cur = dummyHead.next; while (cur != null){ if (cur.e.equals(e)) return true; cur = cur.next; } return false; } /** * 删除索引为0的节点 * @param index */ public E remove(int index){ if (index < 0 || index >= size) { throw new IllegalArgumentException("Delete failed.Illegal index"); } Node pre = dummyHead; for (int i = 0; i < index; i++) { pre = pre.next; } Node delNode = pre.next; pre.next = delNode.next; delNode.next = null; size--; return delNode.e; } public E removeFirst(){ return remove(0); } public E removeLast(){ return remove(size-1); } @Override public String toString() { StringBuilder sb = new StringBuilder(); // sb.append("链表："); Node cur = dummyHead.next; while (cur != null){ sb.append(cur+"->"); cur = cur.next; } sb.append("NULL"); return sb.toString(); } }

测试一下自己写的链表：

public class LinkedListTest { public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < 10; i++) { linkedList.addLast(i); } System.out.println(linkedList); linkedList.add(3,666); System.out.println(linkedList); linkedList.remove(2); System.out.println(linkedList); linkedList.removeFirst(); linkedList.removeLast(); System.out.println(linkedList); } }

输出结果：

3. 用链表实现栈

栈的特点在前面也说过了，主要就是要实现push和pop操作，因为链表的特性，所以将链表的尾部设置为栈底，每push一次，相当于向链表头添加了一个元素，每pop一次相当于删除链表头的元素。 实现代码：

public class LinkedListStack<E> implements Stack { private LinkedList<E> list; public LinkedListStack(){ list = new LinkedList<>(); } @Override public int getSize() { return list.size; } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public void push(Object o) { list.addFirst((E) o); } @Override public E pop() { return list.removeFirst(); } @Override public E peak() { return list.get(0); } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Stack: top "); sb.append(list); return sb.toString(); } }

测试代码：

public class StackTest { public static void main(String[] args) { LinkedListStack<Integer> stack = new LinkedListStack<>(); for (int i = 0; i < 5; i++) { stack.push(i); } System.out.println(stack); stack.pop(); System.out.println(stack); } }

测试结果：

4. 链表实现队列

队列的特点是先进先出，若要用链表实现队列就要搞清楚哪边是队列的头，哪边是尾。假设链表结构如下，由于在tail端删除元素很不容易，只有插入元素比较容易，所以将tail设置为队列尾部，head设置为头部。 这里的链表数据结构和前面的有所不同，增加了一个tail指针，所以需要重新写一下数据结构。

---

首先回顾一下Queue接口： public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront(); }

然后就是用链表实现队列功能：

public class LinkedListQueue<E> implements Queue { private class Node { public E e; public Node next; public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e) { this(e, null); } public Node() { this(null, null); } @Override public String toString() { return e.toString(); } } private Node head , tail; public int size; public LinkedListQueue(){ head = null; tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size==0; } @Override public void enqueue(Object o) { //如果是空的，那就需要将首尾都指向第一个元素 if (tail == null){ tail = new Node((E) o); head = tail; }else { tail.next = new Node((E) o); tail = tail.next; } size ++ ; } @Override public E dequeue() { if (isEmpty()){ throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } Node deNode = head; head = head.next; deNode.next = null; if (head == null) //如果删除后是空的 tail = null; size--; return deNode.e; } @Override public E getFront() { return head.e; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("Queue: front"); Node cur = head; while (cur != null){ sb.append(cur+"->"); cur = cur.next; } sb.append("NULL tail"); return sb.toString(); } }

最后测试一下：

public class LinkedListQueueTest { public static void main(String[] args) { LinkedListQueue<Integer> queue = new LinkedListQueue<>(); for (int i = 0; i < 6; i++) { queue.enqueue(i); System.out.println(queue); if (i%3 == 0){ queue.dequeue(); System.out.println(queue); } } } }

执行结果：