单向链表

什么是单向链表？
链表数据结构是线性数据结构，是真正意义上的动态数据结构，他不需要申请固定的内存空间，是通过代码层面来实现数据的逻辑关系。链表中有个变量名为head的Node节点，Node里面包含要存储的数据和下一个Node节点。

public class LinkedList<E> {
    private Node<E> head;
    private int size;

    public LinkedList() {
    }

    private class Node<E> {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this.e = e;
        }
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append("[");
        Node<E> cur =head;
        while(cur!=null){
            stringBuffer.append(cur.e+",");
            cur = cur.next;
        }
        stringBuffer.append("]");
        return stringBuffer.toString();
    }

添加元素，添加元素其实是找到要插入位置元素的前一个元素节点，然后把前一个Node节点的下一个Node添加到新创建的Node的下一个Node节点，然后再把新创建的节点设置给前一个节点的下一个节点，然后size++;

//指定位置添加元素
public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is error");
        }
        if (index == 0) {
            Node<E> node = new Node<>(e, head);
            head = node;
        } else {
            Node<E> pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            pre.next = new Node(e, pre.next);
        }

        size++;
    }

public void addFirst(E e) {
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

删除元素

 public void removeFirst(){
        head = head.next;
        size--;
    }

    public void removeLast(){
       removeIndex(size-1);
    }

public void removeIndex(int index){
        if(index==0){
            removeFirst();
        }else{
            Node<E> pre = head;
            for (int i = 0; i < index-1; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;
        }
            size--;

    }

public void remove(E e) {
        Node<E> curNode = head;
        //如果表头存储的元素和e是一样的，就找下一个元素，直到表头存储的元素不在和e相等，执行后面while(curNode!=null)
        while (curNode.e.equals(e)) {
            curNode = curNode.next;
            size--;
        }


        while (curNode != null) {
            if (curNode.next.e.equals(e)) {
                curNode.next = curNode.next.next;
                size--;
            } else {
                curNode = curNode.next;
            }
        }
    }

是否包含某个元素,非递归写法

 public boolean contains(E e ){
       Node<E> cur = head;
       while(cur !=null){
           if(cur.e.equals(e)){
               return true;
           }
           cur = cur.next;
       }
       return false;
    }

是否包含某个元素，递归写法,contains(E e)，是用户调用的方法，contains(Node<E> head,E e)是私有方法，内部调用。

 public boolean contains(E e ){
        return contains(head,e);
    }

    private boolean contains(Node<E> head, E e) {

        if(head==null){
            return false;
        }
        if(head.e.equals(e)){
            return true;
        }
        return contains(head.next,e);
    }

全部代码，以下是没有使用虚拟头结点来实现的单向链表。稍微有点复杂。

public class LinkedList<E> {
    private Node<E> head;
    private int size;

    public LinkedList() {
    }

    private class Node<E> {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this.e = e;
        }
    }

    public void addFirst(E e) {
        add(0, e);

    }

    public void addLast(E e) {
        add(size, e);

    }

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is error");
        }
        if (index == 0) {
            Node<E> node = new Node<>(e, head);
            head = node;
        } else {
            Node<E> pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            pre.next = new Node(e, pre.next);
        }

        size++;
    }

    public boolean contains(E e ){
       Node<E> cur = head;
       while(cur !=null){
           if(cur.e.equals(e)){
               return true;
           }
           cur = cur.next;
       }
       return false;
    }
    
    //递归实现
//    public boolean contains(E e ){
//        return contains(head,e);
//    }
//
//    private boolean contains(Node<E> head, E e) {
//
//        if(head==null){
//            return false;
//        }
//        if(head.e.equals(e)){
//            return true;
//        }
//        return contains(head.next,e);
//    }

    public void remove(E e) {
        Node<E> curNode = head;
        while (curNode.e.equals(e)) {
            curNode = curNode.next;
            size--;
        }


        while (curNode != null) {
            if (curNode.next.e.equals(e)) {
                curNode.next = curNode.next.next;
                size--;
            } else {
                curNode = curNode.next;
            }
        }
    }

    public void removeFirst(){
        head = head.next;
        size--;
    }

    public void removeLast(){
       removeIndex(size-1);
    }

    public void removeIndex(int index){
        if(index==0){
            removeFirst();
        }else{
            Node<E> pre = head;
            for (int i = 0; i < index-1; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;
        }
            size--;

    }


    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append("[");
        Node<E> cur =head;
        while(cur!=null){
            stringBuffer.append(cur.e+",");
            cur = cur.next;
        }
        stringBuffer.append("]");
        return stringBuffer.toString();
    }
}

使用虚拟头结点实现的单向链表

public class LinkedList2<E> {
    private Node<E> dummyHead;
    private int size;

    public LinkedList2() {
        dummyHead = new Node<E>();
    }

    private class Node<E> {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this.e = e;
        }

        public Node() {
        }
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is error");
        }

        Node<E> pre = dummyHead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = new Node(e, pre.next);

        size++;
    }

    public void remove(E e) {
        Node<E> curNode = dummyHead.next;
        while (curNode != null) {
            if (curNode.next.e.equals(e)) {
                curNode.next = curNode.next.next;
                size--;
            } else {
                curNode = curNode.next;
            }
        }
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }

    public void removeIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index 错误");
        }
        Node<E> pre = dummyHead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        size--;

    }


    public boolean contains(E e) {
        Node<E> cur = dummyHead.next;
        while (cur != null) {
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append("[");
        Node<E> cur = dummyHead.next;
        while (cur != null) {
            stringBuffer.append(cur.e + ",");
            cur = cur.next;
        }
        stringBuffer.append("]");
        return stringBuffer.toString();
    }
}