public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.add(1);myLinkedList.add(3);myLinkedList.add(5);myLinkedList.add(7);myLinkedList.add(3,4);System.out.println(myLinkedList.toString());System.out.println(myLinkedList.removeFirst());System.out.println(myLinkedList.removeLast());System.out.println(myLinkedList.removeByIndex(1));System.out.println(myLinkedList.toString());}

 先删除头结点，然后删除尾结点，再删除下标为1的数。

2.10删除第一个值为val的元素

想要删除值为的元素，就需要找到它的前驱结点，使前驱节点的与查找元素的后继结点连接，这种时候也需要将头结点单独来看，因为头结点没有前驱结点。

并且如果链表为null这种情况也要分开处理，因为链表为空代表链表中没有值处理不了。

逻辑上的终止条件（假设要删除位置的前驱结点为prev）：此处删除的是prev的后继节点，因此保证prev的后继节点必须存在，所以终止条件是prev.next != null。

    public void removeByValueOnce(int val) {if(head == null){return ;}if(head.val==val){int tmp = head.val;head = head.next;size--;return ;}for(Node prev = head;prev.next!= null;prev = prev.next){if(prev.next.val== val){prev.next = prev.next.next;size--;return;}}}

    public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.add(7);myLinkedList.add(1);myLinkedList.add(3);myLinkedList.add(7);myLinkedList.add(5);myLinkedList.add(3,4);myLinkedList.add(7);System.out.println(myLinkedList.toString());myLinkedList.removeByValueOnce(7);System.out.println(myLinkedList.toString());myLinkedList.removeByValueOnce(7);System.out.println(myLinkedList.toString());myLinkedList.removeByValueOnce(7);System.out.println(myLinkedList.toString());}

2.11在表中删除所有值为val的元素

若链表为空则直接返回，若链表的头结点就是待删除的结点，需要考虑删除后补上的结点的值也是val，所以需要进行while循环，直到head的值不是val，在这种情况中需要让head！=null ，否则无法取得head的val值。

进行完这一步，head可能为空，也可能head的值不是val。同样创建prev进行遍历使 prev= head。所以需要先保证prev不为空，才能取得prev.next的val值。

删除一个结点之后不能直接使prev引用向后走，prev引用直到prev.next.val != val时prev才能向后走，否则如果补上的结点值也为val则会被忽略。

    public void removeAllValue(int val) {if(head == null){return ;}while (head!=null&&head.val==val){int tmp = head.val;head = head.next;size--;}if(head == null){return ;}Node prev = head;while(prev.next!=null){if(prev.next.val== val){prev.next = prev.next.next;size--;}else {prev = prev.next;}}}

    public static void main(String[] args) {MyLinkedList myLinkedList = new MyLinkedList();myLinkedList.add(7);myLinkedList.add(7);myLinkedList.add(3);myLinkedList.add(7);myLinkedList.add(7);myLinkedList.add(5);myLinkedList.add(3,4);myLinkedList.add(7);System.out.println(myLinkedList.toString());myLinkedList.removeAllValue(7);System.out.println(myLinkedList.toString());}

三、带头单链表dummyHead

在单链表的操作过程中，每次插入和删除都需要考虑头结点的情况，因为只有头结点特殊，没有前驱，所以需要想一个办法，让链表中所有的有效结点都一视同仁，就不需要区额外关注头结点的情况。

因此引入一种新的结构，虚拟头结点dummyHead，不存储具体的元素，只是作为链表的头来使用，所有存储元素的结点都是该头结点的后继结点。

3.1结构定义

与单链表不同的地方就是要在构造方法中先定义虚拟头结点。后来每一个结点都在虚拟头结点的后面。

public class LinkedListWithHead {private int size;private Node dummyHead;private static class Node {private int val;private Node next;public Node(int val) {this.val = val;}}public LinkedListWithHead(){this.dummyHead = new Node(-1);}
}

3.2中间位置的插入

首先排除不合法情况后不需要将第一个有效结点单独拿出来调用头插法，因为它也有前驱结点，所以可以一视同仁。

    public void add(int index, int val){if (index < 0 || index > size) {throw new IllegalArgumentException("add index illegal!");}Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}Node node = new Node(val);node.next = prev.next;prev.next = node;size++;}

3.3头插法和尾插法

 与单链表没有什么差别，就是将单链表的头结点换成了带头链表的虚拟头结点的后继节点。

    public void addFirst(int val){Node node = new Node(val);node.next = dummyHead.next;dummyHead.next = node;size++;}

 但是在带头链表中，第一个有效结点也有前驱节点，所以也可以像尾插法一样运用add方法。

    public void addFirst(int val){add(0,val);}public void addLast(int val) {add(size,val);}

 3.4遍历带头链表

经过链表之后，带头链表的遍历就很好写了，摘除头结点之后遍历即可。

    public String toString() {StringBuilder sb = new StringBuilder();Node cur = dummyHead.next;while (cur != null) {sb.append(cur.val);sb.append("->");if (cur.next == null) {sb.append("NULL");}cur = cur.next;}return sb.toString();}

    public static void main(String[] args) {LinkedListWithHead linkedListWithHead = new LinkedListWithHead();linkedListWithHead.addLast(3);linkedListWithHead.addLast(5);linkedListWithHead.addLast(9);linkedListWithHead.addFirst(1);linkedListWithHead.add(3,7);System.out.println(linkedListWithHead.toString());}

 先尾插3,5,9。然后头插1，在指定位置3插入7。

3.5 在表中删除所有值为val的元素

具体逻辑也是和单链表一样的，只是不需要特别考虑头结点。用cur指向虚拟头结点，来判断cur.next的val是否和需要判断的值相同，如果相同就将cur.next指向 cur.next.next，直到不相同的时候，就让cur向右移。

    public void removeAllValue(int val){Node cur = dummyHead;while (cur.next!=null){Node sec = cur.next.next;if(cur.next.val == val){cur.next = sec;size--;}else{cur = cur.next;}}}

    public static void main(String[] args) {LinkedListWithHead linkedListWithHead = new LinkedListWithHead();linkedListWithHead.addLast(1);linkedListWithHead.addLast(1);linkedListWithHead.addLast(3);linkedListWithHead.addLast(1);linkedListWithHead.addLast(5);linkedListWithHead.addLast(1);linkedListWithHead.addFirst(1);System.out.println(linkedListWithHead.toString());linkedListWithHead.removeAllValue(1);System.out.println(linkedListWithHead.toString());}

 四、用递归写链表的方法

具体构造还是和之前一样。

public class LinkedListR implements SeqList {private int size;private Node head;private  class Node {private int val;private Node next;public Node(int val) {this.val = val;}}
}

4.1链表指定位置的插入

首先就是不合法情况的排除，然后先判断如果index==0就是头插法，如果index!=0，那么直接让head.next = add(head.next,index - 1,val)，调用递归一直到找到index位置然后插入即可。

然后头插和尾插都调用这个方法输入对应的位置即可。

    public void addFirst(int val) {add(0,val);}@Overridepublic void add(int val) {add(size,val);}@Overridepublic void add(int index, int val) {if (index < 0 || index > size) {throw new IllegalArgumentException("add index illegal!");}head = add(head,index,val);}private Node add(Node head, int index, int val) {if (index == 0) {Node node = new Node(val);node.next = head;head = node;size ++;return head;}head.next = add(head.next,index - 1,val);return head;}

4.2链表的正向输出

链表的正向输出用递归写也很简单，首先head==null时，输出NULL然后返回即可，然后先输出当前的值在调用递归，一个接一个输出。

    private void print(Node head) {if (head == null) {System.out.print("NULL\n");return;}System.out.print(head.val + "->");print(head.next);}public void print() {print(head);}

4.3链表的反向输出

用递归的方法反向输出会更加的容易，能倒叙从尾结点开始输出内容，一直到头结点。

首先当head==null时，直接返回就好，然后需要把先把子链表全部输出完，站在head位置，只要一直输出就好。但是这个时候最后输出没有办法加上null，正常正向输出最后会有null，所以创建一个变量count计数，在每次调用递归前count++。然后每次调用完递归返回后再count--，当count==0时，已经走到了链表的头结点，在最后要继续输出null。

    public void printReverse() {printReverse(head);}int count = 0;private void printReverse(Node head) {if (head == null) {return;}count ++;printReverse(head.next);count --;System.out.print(head.val + "->");if (count == 0) {System.out.print("NULL\n");}}

    public static void main(String[] args) {LinkedListR list = new LinkedListR();list.addFirst(1);list.addFirst(3);list.add(5);list.add(7);list.add(1,10);list.print();list.printReverse();}

五、ArrayList和LinkedList的区别