JavaDS —— 单链表 与 LinkedList

顺序表和链表区别

ArrayList ：
底层使用连续的空间，可以随机访问某下标的元素，时间复杂度为O（1）
但是在插入和删除操作的时候，需要将该位置的后序元素整体往前或者向后移动，时间复杂度为O（N）
增容需要申请新空间，有时候需要拷贝数据释放旧空间，这会有不小的消耗。
顺序表的增容一般是2倍增加的，势必会有一定的kong’jian浪费，例如当前容量为100时，需要扩容的话，就是将容量增加到200，如果只是再插入几个数据，就一定会浪费九十几的空间。

既然如此，我们就会思考如何减少空间的浪费，这时候链表就登场了，下面是单链表的示意图：

链表由两个部分组成，一个是数据域，一个是指针域，数据域是用来存放数据的，指针域是用来存放下一个或者前一个的引用的，这样就把数据给串联起来了，大家也就不难发现，链表的优点就是用多少空间就申请多少空间，做到空间不浪费，并且在下面的内容，你还会感受到链表的插入删除操作效率很高。

链表的分类

链表有8大类，带头和不带头，单向还是双向，循环还是不循环，2^3 = 8种

带头和不带头是指链表有没有一个哨兵节点，就是只是充当头结点的作用，不存放任何有效的数据。
上面的图片就是不带头的，下面的是带头的：

单向和双向是指：链表的节点是只指向后一个节点的话就是单向的，如果链表的节点即指向前一个结点又指向后一个节点的话就是双向的。

循环和不循环是指链表是否头尾相连，如果头尾相连就是循环的，否则就是不循环的：

实现单链表

下面是自己写的IList接口，会被单链表拓展：

public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();//清空链表public void clear();//打印链表public void display();
}

单链表的节点需要一个数据域和一个指针域，我们先来写一个静态内部类来构造节点类：

    static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}

除此之外，我们还需要一个头指针来指向第一个节点：

    public ListNode head;

打印

循环遍历链表，打印每一个节点的数据，这个方法有利于我们的测试：

    @Overridepublic void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}

头插

在单链表的头部插入一个数据，我们需要将新头节点的next指向原先头部的节点，然后改变head的指向。

    @Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}

尾插

循环遍历单链表找到尾节点，然后改变尾节点的指向即可。

这里要注意如果head为空的时候，直接赋值就可以了，不能直接使用null，会报空指针异常，所以在循环前面加多一个判断条件即可。

    @Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;return;}ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = node;}

求节点总个数

这个很简单，直接循环遍历即可。

    @Overridepublic int size() {ListNode cur = head;int count = 0;while(cur != null) {cur = cur.next;count++;}return count;}

指定位置插入

先判断指定的位置有没有越界，和之前的顺序表是一样的，这里不赘述：

public class IndexException extends RuntimeException{public IndexException(String message) {super(message);}
}

    private void checkIndexInAdd(int index) throws IndexException {if(index < 0 || index > size()) {throw new IndexException("下标范围不合法！");}}

---

我们要先找到index前一个结点，因为这个插入操作是对三个节点进行操作的，首先先把index的引用放入新结节点的next中，然后再把index前一个结点的next改成新结点的引用，这是一般情况，如果index == 0的话就是头插操作，为什么要做一个判断，因为我们得出的一般规律最后是cur.next = node，这是建立在新结点前面一定有结点的情况下，但是如果是头插的话就不符合了，所以头插需要单独说明。

    @Overridepublic void addIndex(int index, int data) {try{checkIndexInAdd(index);if(index == 0) {addFirst(data);return;}//找到index前一个的节点ListNode cur = head;for (int i = 0; i < index - 1; i++) {cur = cur.next;}ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;} catch (IndexException e) {System.out.println("index 不合法！");e.printStackTrace();}}

对于插入操作，我们要先处理后面的结点，避免后面的结点丢失。

contains

是否包含某个元素，直接遍历循环即可：

    @Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}

删除第一次出现的key

删除某个结点的时候，由于这是单链表，所以我们最好事先拿到删除节点的前一个结点，然后我们要考虑一些特殊的情况，如果这个链表为空就不需要删除，如果要删除的结点就是头结点，那么我们就需要改变头指针的指向，最后就是一般情况下，我们直接修改删除结点的前一个结点的 next 域 就可以了。

    private ListNode findFrontNodeOfKey(int key) {ListNode cur = head;while(cur != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;}@Overridepublic void remove(int key) {//空链表if(head == null) {return;}//头删if(head.val == key) {head = head.next;return;}ListNode prev = findFrontNodeOfKey(key);if(prev == null) {return;//不存在key}ListNode del = prev.next;prev.next = del.next;}

删除所有出现的key

我们使用两个指针，一个从头结点开始，另一个从头结点的下一个结点开始遍历链表，当第二个指针遇到要删除的结点时，配合第一个指针完成此工作，然后prev不变，cur继续移动，如果没有遇到删除的结点，两个指针是一起继续向后运动。

要注意如果链表为空的话就直接return ，避免发生空指针异常

这时候大家一定知道还差一个结点没有判断，就是第一个结点，所以我们最后还有判断一下头结点。

    @Overridepublic void removeAllKey(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;} else {prev = cur;}cur = cur.next;}if(head.val == key) {head = head.next;}}

clear

清空链表，你可以直接把头指针赋值为null，由于链表没有被引用，会被JVM自动回收，

    @Overridepublic void clear() {ListNode cur = head;while(cur != null) {ListNode tmp = cur.next;cur.next = null;cur = tmp;}head = null;}

模拟实现LinkedList

LinkedList 是不带头，双向的，循环的链表

构建节点

双向的意味着有两个节点，一个指向前一个结点，一个指向后一个结点，还有一个头指针指向头节点，一个尾指针指向尾节点。

    static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;

打印

    public void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}

头插

要注意如果头指针为null，意味着链表为空，尾指针自然也是null，链表为空的话，插入新数据要改变头尾指针的指向。
正常情况下是链表至少有一个结点，改变原先头节点的prev指向，新结点的next也要改变。

    public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null) {head = last = node;return;}head.prev = node;node.next = head;head = node;}

尾插

注意如果尾指针为null时，说明链表为空。和上面的头插一样，要单独讨论说明。

    public void addLast(int data) {ListNode node = new ListNode(data);if(last == null) {head = last = node;}last.next = node;node.prev = last;last = node;}

求结点个数

    public int size() {ListNode cur = head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}

指定位置插入

先判断index是否合法，不合法还是和之前一样抛异常。

public class IndexOutOfBoundException extends RuntimeException {public IndexOutOfBoundException() {super();}public IndexOutOfBoundException(String message) {super(message);}
}

    private void checkIndexInAdd(int index) throws IndexOutOfBoundException{if(index < 0 || index > size()) {throw new IndexOutOfBoundException("下标越界！！！");}}

我们先讨论一般情况，如果待插入的结点正好前后都是由结点的，那么我们需要修改三个结点的指针：
cur.prev.next = node;
node.prev = cur.prev;
node.next = cur;
cur.prev = node;

现在来注意特殊情况，如果index == 0时，就是头插，不管怎么样，头插就一定要改变头指针，所以要单独讨论。换一种思路，如果是头插的话，cur.prev = null ，所以 cur.prev.next 一定会报空指针异常。所以头插还是要单独讨论。
那如果是尾插呢？尾插意味着 cur == null ,还是和头插思考方式一样，尾节点一定要改变所以要单独讨论，还有cur.prev 一定会报空指针异常。

    public void addIndex(int index,int data) {try {checkIndexInAdd(index);if(index == 0) {addFirst(data);return;}ListNode node = new ListNode(data);ListNode cur = head;for (int i = 0; i < index; i++) {cur = cur.next;}if(cur == null) {addLast(data);return;}cur.prev.next = node;node.prev = cur.prev;node.next = cur;cur.prev = node;} catch (IndexOutOfBoundException e) {e.printStackTrace();}}

remove

删除第一次出现关键字为key的节点

如果链表为空不能继续删除操作
如果删除头节点，就必须改变头指针，所以要单独说明
一般情况下，需要变动cur前后结点，自然会想到：cur.prev.next = cur.next; cur.next.prev = cur.prev;
那如果是尾删呢？上面两行代码只有前面一行还能继续用，由于是尾删，尾节点就要发生改变，所以last = cur.prev;

public void remove(int key) {if(head == null) {return;}if(head.val == key) {head = head.next;if(head != null) {head.prev = null;}return;}ListNode cur = head.next;while(cur != null) {if(cur.val == key) {cur.prev.next = cur.next;if(cur.next == null) {last = cur.prev;} else {cur.next.prev = cur.prev;}return;}cur = cur.next;}}

removeAllKey

删除所有值为key的节点

删除所有的key，上面我们写了删除第一次出现key的结点，这里把代码直接帮过来，删掉return就可以继续用，但是一定是对的吗？
前面的链表判空直接返回没有问题，但是头删的话就有问题了，假设头节点是你要删除的结点就意味着头指针要发生改变，那如果新的头节点又要发生改变呢？这里我们选择尽量不改变我们的祖传代码，把头删放在最后面去做即可。

    public void removeAllKey(int key) {if(head == null) {return;}ListNode cur = head.next;while(cur != null) {if(cur.val == key) {cur.prev.next = cur.next;if(cur.next == null) {last = cur.prev;} else {cur.next.prev = cur.prev;}}cur = cur.next;}if(head.val == key) {head = head.next;if(head != null) {head.prev = null;}}}

contains

是否包含key这个元素

    public boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}

clear

你可以直接将head 和last都置为null，这样链表就会被JVM自动回收。
这里模仿源码的写法，源码是一个一个结点都置为null，最后头尾指针再置为null

    public void clear() {ListNode cur = head;while(cur != null) {ListNode tmp = cur.next;cur.prev = null;cur.next = null;cur = tmp;}head = last = null;}

LinkedList 使用

Java集合类中给我们提供了LinkedList，这是一个无头双向循环链表，我们来看一下它里面的方法，方法名字和上面我们模拟实现的差不多。

LinkedList 的构造方法

第二个构造方法是可以传入一个对象，和之前ArrayList表示二维数组是一个意思。

LinkedList 的方法

要注意LinkedList和ArrayList 的subList是一样的原理，截取的list还是原来的对象list，只是范围不同，并没有创建新的对象。

add（默认尾插）

注意LinkedList的add方默认是尾插：

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);}

addAll

尾插一个对象

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);ArrayList<Integer> list1 = new ArrayList<>();list1.add(10);list1.add(20);list.addAll(list1);System.out.println(list);}

遍历链表

直接打印

LinkedList也是重写了toString 方法

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);}

for 循环

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);int size = list.size();for (int i = 0; i < size; i++) {System.out.print(list.get(i) + " ");}System.out.println();}

for each

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);for(int x : list) {System.out.print(x + " ");}System.out.println();}

迭代器

ListIterator 是继承 Iterator 的，这两个都可以来遍历链表打印数据。

迭代器的使用可以类似下面的图：

while（it.hasNext()）hasNext表示是否由下一个数据，通过next（）方法打印下一个数据，之后 it 一直向后移动。

Iterator

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println("===== Iterator ====");Iterator<Integer> it = list.iterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();}

ListIterator

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);ListIterator<Integer> lit =  list.listIterator();while (lit.hasNext()) {System.out.print(lit.next()+" ");}System.out.println();}

ListIterator(逆向遍历)

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println("===== ListIterator ====");ListIterator<Integer> lit2 =  list.listIterator(list.size());while (lit2.hasPrevious()) {System.out.print(lit2.previous()+" ");}System.out.println();}

listIterator(int n) ，可以指定从哪个下标开始遍历链表

ArrrayList 和 LinkedLisrt 的总结

配套练习：
http://t.csdnimg.cn/nmObG