一.链表

1.链表定义

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点的引用，该节点含有一个泛型的元素和一个指向另一条链表的引用。
在这个定义中，结点是一个可能含有任意类型数据类型的抽象实体，它所包含的指向结点的应用显示了它在构造构造链表中的用处。

2.动态链表

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身的元素外，还要存储一个指示其直接后继信息。我们把存储数据元素的称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或是链。这两部分信息组成的数据元素ai的存储映像，称为结点(Node);多个结点链接成一个链表，即线性表的链式存储结构，如图：

头结点与头指针
头结点是指链表的第一个结点，有真实头结点和虚拟头结点的划分。
真实头结点：第一个结点用于存储数据；虚拟头结点第一个结点不存储数据。

头指针：就是一个引用变量，用于存储头结点的地址；
尾指针：也一样，就是链表中最后一个结点的指针。

3.单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

3.1代码实现

还是继承顺序表定义的List接口，然后实现每个功能。

3.1.1结点定义

定义Node结点类型，采用泛型，定义数据域，指针域两个成员变量，
然后实现构造函数分别是无参，一个参数，两个参数的构造方法。

 //定义内部类Node节点对象private class Node{E data; //数据域Node next;//指针域public Node(){this(null,null);}public Node(E data){this(data,null);}public Node(E data,Node next){this.data = data;this.next = next;}

3.1.2链表的成员变量定义

定义头尾指针head，tail，元素个数size;默认构造函数中将头尾指向null，元素个数置为0。因为默认没有元素，我们的头尾指针指向null，如图：

package lianbiao;import ifce.List;import java.util.Comparator;
import java.util.Iterator;public class LinkedSinglyList<E> implements List<E> {//结点内部类@Overridepublic String toString() {return data.toString();}}private  Node head;private Node tail;private int size;public LinkedSinglyList(){head = null;tail = null;size = 0;}

3.1.3将一个数组转换为链表。

主要依靠元素添加方法实现，就是遍历数组将其逐个插入链表当中。

    public LinkedSinglyList(E[] arr){if(arr == null || arr.length == 0){throw new IllegalArgumentException("arr is null");}for(int i=0;i<arr.length;i++){add(arr[i]);}}

3.1.4添加元素

我们添加元素分为直接添加元素，默认往尾部添加；还有按角标添加元素，所以第一个调用第二个即可，我们实现第二个。
按角标添加分为四种，当然我们首先需要判断角标是否越界，不越界则进行添加；
第一种：没有元素时添加；
第二种往头部添加；
第三种往尾部添加；
第四种就是往中间添加；我们分别用图来看一下：

 @Overridepublic void add(E element) {add(size,element);}@Overridepublic void add(int index, E element) {if(index < 0 || index > size){throw new IllegalArgumentException("index 越界");}Node n = new Node(element);if(size == 0){head = n;tail = n;}else if(index == 0){n.next = head;head = n;}else if(index == size){tail.next = n;tail = n;}else{Node p = head;for(int i = 0;i<index-1;i++){p = p.next;}n.next = p.next;p.next = n;}size++;}

3.1.5删除元素

和添加元素一样，也有几种情况。参数为数据的调用参数为角标的删除方法即可。
先判角标越界，因为要返回删除元素，则定义一个变量用于保存删除元素；然后分情况：
第一种：只有一个元素删除；
第二种：从头部删除元素；
第三种：从尾部删除元素；
第四种：从中间删除元素；还是看图分析：

@Overridepublic void remove(E element) {remove(element);}@Overridepublic E remove(int index) {if(index < 0 || index > size){throw new IllegalArgumentException("index 越界");}E ret = null;if(size == 1){ret = head.data;head = null;tail = null;}else if(index == 0){Node n = head;ret = n.data;head = n.next;n.next = null;}else if(index == size-1){Node p = head;while(p.next != tail){p = p.next;}ret = tail.data;p.next = null;tail = p;}else{Node p = head;for(int i = 0;i<index-1;i++){p = p.next;}Node n = p.next;p.next = n.next;n.next = null;}size--;return ret;}

3.1.6通过角标查看元素和修改元素

查看和修改步骤几乎一样，只是查看是直接返回元素，而修改无非就是定义一个变量对值进行存储，再进行赋值修改后，将保存的值返回。
他有三种情况：查看修改头元素；直接head.data就能拿到。尾元素就是通过tail.data。对于中间元素，我们就需要从0-index遍历去找，然后进行查看或是修改。

 @Overridepublic E get(int index) {if(index<0|| index>=size){throw  new IllegalArgumentException("get index out of range");}if(index == 0){return head.data;}else if(index == size - 1){return tail.data;}else{Node p = head;for(int i = 0;i<index;i++){p=p.next;}return p.data;}}@Overridepublic E set(int index, E element) {if(index<0|| index>=size){throw  new IllegalArgumentException("get index out of range");}E ret = null;if(index == 0){ret = head.data;head.data = element;}else if(index == size - 1){ret = tail.data;tail.data = element;}else{Node p = head;for(int i = 0;i<index;i++){p=p.next;}ret = p.data;}return ret;}

3.1.7通过元素找角标

定义一个角标，从head头结点遍历，只要元素不等就往后遍历然后角标加1，如果遍历完，没找到，则返回-1；找到则返回对应的下标即可。

@Overridepublic int indexOf(E element) {Node p = head;int index = 0;while (!p.data.equals(element)){p = p.next;index++;if(p == null){return -1;}}return index;}

3.1.8排序

使用了选择排序；定义两个指针结点，外层循环从head开始遍历,到倒数第二个元素结束即可。内层循环从head的下一个结点开始，到最后一个结点结束。

@Overridepublic void sort(Comparator<E> c) {if(c == null){throw new IllegalArgumentException("comparator is null");}if(size == 0 || size == 1){return;}Node nodeA = head;Node nodeB = nodeA.next;while (true){while (true){if(c.compare(nodeA.data,nodeB.data)>0){swap(nodeA,nodeB);}if(nodeB == tail){break;}nodeB = nodeB.next;}if(nodeA.next == tail){break;}nodeA = nodeA.next;nodeB = nodeA.next;}}private void swap(Node nodeA, Node nodeB) {E temp = nodeA.data;nodeA.data = nodeB.data;nodeB.data = temp;}

3.1.9切割子串

因为我们实现的是单向链表，所以不能向前遍历，所以找一个元素需要从前往后遍历查找；分别找到fromIndex，toIndex对应在链表中的位置。然后逐一添加进链表即可。

@Overridepublic List<E> subList(int fromIndex, int toIndex) {if(fromIndex<0 || toIndex>=size|| fromIndex > toIndex){throw new IllegalArgumentException("must 0 <= fromIndex <= toIndex <= size - 1");}LinkedSinglyList<E> list = new LinkedSinglyList<>();Node nodeA = head;for(int i = 0;i<fromIndex;i++){nodeA = nodeA.next;}Node nodeB = head;for(int i = 0;i<toIndex;i++){nodeB = nodeB.next;}Node p = nodeA;while(true){list.add(p.data);if(p == nodeB){break;}p = p.next;}return list;}

3.1.10toString方法，与迭代器的实现。

tostring与顺序表的相似。迭代器定义变脸指向head结点，只要该变量不指向null，就表示有元素，那让角标移动一次，返回对应值。

@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("[");if (isEmpty()) {sb.append("]");} else {Node p = head;while (true) {sb.append(p.data);if (p == tail) {sb.append("]");break;}sb.append(",");sb.append(" ");p = p.next;}}return sb.toString();}@Overridepublic Iterator<E> iterator() {return new LinkedSinglyListIterator();}class LinkedSinglyListIterator implements Iterator<E>{private Node cur = head;@Overridepublic boolean hasNext() {return cur != null;}@Overridepublic E next() {E ret = cur.data;cur = cur.next;return ret;}}

3.1.11其他方法实现

@Overridepublic int size() {return size;}
@Overridepublic boolean contains(E element) {return indexOf(element) != -1;}@Overridepublic boolean isEmpty() {return size == 0 && head == null && tail == null;}@Overridepublic void clear() {head = null;tail = null;size = 0;}

3.单向循环链表

他是在单向链表的基础上加一点点改进，主要是让我们的链表遍历都尾部，重新回到头部，形成了一个环。就是在单链表的基础上某些方法做一点改进，所以我们改一下代码；
需要修改代码的方法如下：

@Overridepublic void add(int index, E element) {if(index < 0 || index > size){throw new IllegalArgumentException("index 越界");}Node n = new Node(element);if(size == 0){head = n;tail = n;tail.next = head;//new code 将链表尾与头部链接起来。}else if(index == 0){n.next = head;head = n;tail.next = head;//new code}else if(index == size){n.next = tail.next; //new codetail.next = n;tail = n;}else{Node p = head;for(int i = 0;i<index-1;i++){p = p.next;}n.next = p.next;p.next = n;}size++;}@Overridepublic E remove(int index) {if(index < 0 || index > size){throw new IllegalArgumentException("index 越界");}E ret = null;if(size == 1){ret = head.data;head = null;tail = null;}else if(index == 0){Node n = head;ret = n.data;head = n.next;n.next = null;tail.next = head;//new code}else if(index == size-1){Node p = head;while(p.next != tail){p = p.next;}ret = tail.data;p.next = tail.next;//change code原先是指向null，因为单向链表尾部的下一个元素是null，而对于我们的单向循环链表来说，最后一个元素的下一个元素就是head；tail = p;}else{Node p = head;for(int i = 0;i<index-1;i++){p = p.next;}Node n = p.next;p.next = n.next;n.next = null;}size--;return ret;}@Overridepublic int indexOf(E element) {Node p = head;int index = 0;while (!p.data.equals(element)){p = p.next;index++;if(p == head){ //change code还是一样，单链表最后一个元素指向null，而单向循环链表则指向head。return -1;}}return index;}@Overridepublic Iterator<E> iterator() {return new LinkedSinglyCircularListIterator();}class LinkedSinglyCircularListIterator implements Iterator<E>{private Node cur = head;//根据圈数判断是否存在元素private boolean flag = true;@Overridepublic boolean hasNext() {if(isEmpty()){return false;}//建立在链表不为空情况下return flag;}@Overridepublic E next() {E ret = cur.data;cur = cur.next;if(cur == head){flag = false;}return ret;}}
}

测试

遍历目录结构，将名录名，极其目录下的目录或文件名打印出来。

public class TestLinkedSinglyList {public static void main(String[] args) {LinkedSinglyCircularList<Integer> list = new LinkedSinglyCircularList();list.add(1);list.add(5);list.add(3);list.add(9);list.add(4);list.add(8);System.out.println(list.toString());list.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});System.out.println(list);}
}

4.双向循环链表LinkedList

双向循环链表是链表的一种，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱。所以我们可以从前，从后遍历我们的链表。如图：

4.1结点类型定义

还是定义一个Node类型的内部类，定义前驱指针pre，后继指针next，数据域data，还有我们的构造方法，以及返回数据的toString方法。

class Node{E data;private Node pre;private Node next;public Node(){this(null,null,null);}public Node(E data){this(data,null,null);}public Node(E data,Node pre,Node next){this.data = data;this.pre = pre;this.next = next;}@Overridepublic String toString() {return data.toString();}}

4.2LinkedList成员变量定义及其构造方法

定义头尾结点head，tail，还有元素个数size属性；无参构造是创建一个默认的链表，默认是空的，所以head，tail指向null，size为0；另一个带参构造方法传入一个数组，将其转换为链表，我们是直接将数组中每个元素拿出逐个遍历添加到链表中。

public class LinkedList<E> implements List<E>, Deque<E>, Stack<E> {private  Node head;private  Node tail;private  int size;public LinkedList(){head = null;tail = null;size = 0;}public LinkedList(E[] arr){if(arr == null){throw  new IllegalArgumentException("arr is null");}for(int i = 0;i<arr.length;i++){add(arr[i]);}}

4.3添加元素

先判断角标越界，然后分情况讨论：
第一种：没有元素时添加；
第二种：从头部添加；
第三种：从尾部添加；
第四种：从中间添加；
第一种比较简单：因为默认head和tail是指向null，所以直接让它们指向新的元素就好，然后建立循环，让head的前驱指向tail，让tail的直接后继指向head；
第二种：

第三种和第二种相似，它是倒过来的。

第四种：

@Overridepublic void add(E element) {add(size,element);}@Overridepublic void add(int index, E element) {if(index < 0 || index > size){throw  new IllegalArgumentException("index out of range");}Node n = new Node(element);if(size == 0){head = n;tail = n;tail.next = head;head.pre = tail;}else if(index == 0){n.pre = head.pre;n.next = head;head.pre = n;head = n;tail.next = head;}else if(index == size){tail.next = n.next;tail.next = n;n.pre = tail;tail = n;head.pre = tail;}else{Node p,q;if(index <= size / 2){p = head;for(int i = 0;i<index-1;i++){p = p.next;}q = p.next;p.next = n;n.pre = p;q.pre = n;n.next = q;}else {p = tail;for(int i = size -1;i> index;i--){p = p.pre;}q = p.pre;q.next = n;n.pre =q;n.next = p;p.pre = n;}}size++;}

4.4删除元素

删除元素和添加元素的套路相似，但有些又有不同。
第一种：只有一个元素，那删除就成了空链表，所以直接让头尾结点指向null；
第二种：从头部删除：

第三种是第二种的反向；
先找新的tail，node = tail.pre;然后切断tail到node的连接；tail.pre = null;然后更新从tail到head的环链接，node.next = tail.next,再将tail对 head的连接断开，tail.next =null;再更新tail；tail=node；再将从head到tail的环链接更新；head.pre = tail.

@Overridepublic void remove(E element) {int index = indexOf(element);if(index != -1){remove(index);}}@Overridepublic E remove(int index) {if(index < 0 || index >= size){throw  new IllegalArgumentException("index out of range");}E ret = null;Node node;if(size == 1){ret = head.data;head = null;tail = null;}else if(index == 0){ret = head.data;node = head.next;head.next = null;node.pre = head.pre;head.pre = null;head = node;tail.next = head;}else if(index == size-1){ret = tail.data;node = tail.pre;tail.pre = null;tail.next = node.next;tail.next = null;tail = node;head.pre = tail;}else {Node p,q,r;if(index <= size/2){p = head;for(int i=0;i< index -1;i++){p = p.next;}q = p.next;r = q.next;ret = q.data;p.next = r;r.pre =p;q.next = null;q.pre = null;}else {p = tail;for(int i=size-1;i< index +1;i--){p = p.pre;}q = p.pre;r = q.pre;ret = q.data;r.next = p;p.pre = r;q.pre = null;q.next = null;}}size--;return ret;}

4.5通过角标查看元素以及修改元素

先判断角标是否越界，然后就是查看头，就返回head.data,查看尾，则返回tail.data,查看中间元素那就遍历从0到角标index，找到对应的结点，然后返回它的元素即可；
修改无非是先将对应的数据保存起来，然后在再修改元素的值，最后将值返回。

@Overridepublic E get(int index) {if(index < 0 || index >= size){throw new IllegalArgumentException("index out of rang");}if(index == 0){return head.data;}else if(index == size-1){return tail.data;}else{Node p = head;for(int i = 0;i<index;i++){p = p.next;}return p.data;}}@Overridepublic E set(int index, E element) {if(index < 0 || index >= size){throw new IllegalArgumentException("index out of rang");}E ret = null;if(index == 0){ret = head.data;head.data = element;}else if(index == size-1){ret = tail.data;tail.data = element;}else{Node p = head;for(int i = 0;i<index;i++){p = p.next;}ret = p.data;}return ret;}

4.6排序方法

先判断构造器是否null，然后是链表只有一个元素或者没有元素那就没有排序的必要。我们用的是插入排序；

 @Overridepublic void sort(Comparator<E> c) {if(c == null){throw  new IllegalArgumentException("comparator is null");}if(size == 0 || size == 1){return;}for (Node nodeA = head.next;nodeA != head;nodeA = nodeA.next){E e = nodeA.data;Node nodeB,nodeC;for(nodeB = nodeA,nodeC=nodeB.pre; nodeC != tail && c.compare(nodeC.data,e)>0;nodeB=nodeB.pre,nodeC=nodeC.pre){nodeB.data = nodeC.data;}nodeB.data = e;}}

4.7关于栈的方法

栈调用的是队列的方法实现自己的操作。

@Overridepublic void push(E element) {addLast(element);}@Overridepublic E pop() {return removeLast();}@Overridepublic E peek() {return getLast();}

4.8关于队列的方法

关于Queue的方法主要是通过Deque的方法实现，而Deque则是调用我们的LinkedList的增删查方法

@Overridepublic void offer(E element) {addLast(element);}@Overridepublic E poll() {return removeFirst();}@Overridepublic E element() {return getFirst();}//Deque@Overridepublic void addFirst(E element) {add(0,element);}@Overridepublic void addLast(E element) {add(size,element);}@Overridepublic E removeFirst() {return remove(0);}@Overridepublic E removeLast() {return remove(size-1);}@Overridepublic E getFirst() {return get(0);}@Overridepublic E getLast() {return get(size-1);}

4.9其他方法

这里的方法和我们的单向循环链表的方法实现是一模一样的。

@Overridepublic int size() {return size;}@Overridepublic int indexOf(E element) {Node p = head;int index = 0;while (!p.data.equals(element)){p=p.next;index++;if(p == head){return -1;}}return index;}@Overridepublic boolean contains(E element) {return indexOf(element) != -1;}@Overridepublic boolean isEmpty() {return size == 0 && head==null && tail == null;}@Overridepublic void clear() {head = null;tail = null;size = 0;}
@Overridepublic List<E> subList(int fromIndex, int toIndex) {if(fromIndex<0 || toIndex >= size || fromIndex < toIndex){throw new IllegalArgumentException("0<=fromIndex<=toIndex<=size-1");}Node nodeA = head;for(int i = 0;i<fromIndex;i++){nodeA = nodeA.next;}Node nodeB = head;for(int i = 0;i<toIndex;i++){nodeB = nodeB.next;}Node p = nodeA;LinkedList<E> list = new LinkedList<>();while(true){list.add(p.data);if(p == nodeB){break;}p = p.next;}return list;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("[");if (isEmpty()) {sb.append("]");} else {Node p = head;while (true) {sb.append(p.data);if (p == tail) {sb.append("]");break;}sb.append(",");sb.append(" ");p = p.next;}}return sb.toString();}@Overridepublic Iterator<E> iterator() {return new LinkedListIterator();}class LinkedListIterator implements Iterator<E>{private Node cur = head;private boolean flag = true;@Overridepublic boolean hasNext() {if(isEmpty()){return false;}//建立在链表不为空情况下return flag;}@Overridepublic E next() {E ret = cur.data;cur = cur.next;if(cur == head){flag = false;}return ret;}}