链表：单链表的实现

链表实现过程中的要点：

1、理解指针或引用的定义
2、小心指针的丢失或内存泄漏
3、利用辅助虚拟头结点简化实现难度
4、留意边界
5、利用画图解决问题

时间复杂度
随机访问：O(n)
插入删除：O(1)

结点类

linkedlist.PNG

class Node{
        public E e;
        public Node next;

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

        }

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

        public Node(E e) {
            this(e, null);
        }
    }

接口类

public interface LinkedList<E> {

    public int size();
    public void add(int index,E e);
    public void addFirst(E e);
    public void addLast(E e);
    public E remove(int index);
    public E removeFirst();
    public E removeLast();
    public E get(int index);
    public void set(int index ,E e);
    public boolean contains(E e);
    public boolean isEmpty();
}

实现类

public class LinkedListImpl<E> implements LinkedList<E> {
    //结点类
    class Node{
        public E e;
        public Node next;

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

        }

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

        public Node(E e) {
            this(e, null);
        }
    }

    private int size;//链表中的元素个数
    private Node dummyHead;//虚拟头结点;
    //初始化
    public LinkedListImpl(){
        dummyHead = new Node();
        size = 0;
    }
    @Override
    public int size() {
        return size;
    }

    @Override
    public void add(int index , E e) {
        //边界处理
        if (index < 0 || index > size )
            throw new IllegalArgumentException("the index is illegal,add is fail");

        Node pre = dummyHead;

        for (int i = 0 ; i < index ;i++ ){
            pre = pre.next;
        }

        Node node = new Node(e);
        node.next = pre.next;
        pre.next = node;

        size++;
    }

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

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

    }

    @Override
    public E remove(int index) {
        if (index < 0 || index >= size )
            throw new IllegalArgumentException("the index is illegal,remove is fail");

        Node pre = dummyHead;

        for (int i = 0 ; i < index ; i++ ){
            pre = pre.next;
        }
        E re = pre.next.e;
        pre.next = pre.next.next;
        size --;

        return re;
    }

    @Override
    public E removeFirst() {
        return remove(0);

    }

    @Override
    public E removeLast() {
        return remove(size-1);
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size )
            throw new IllegalArgumentException("the index is illegal,get is fail");

        Node node = dummyHead.next;

        for (int i = 0 ; i < index ; i++ ){
            node = node.next;
        }

        return node.e;
    }

    @Override
    public void set(int index, E e) {
        if (index < 0 || index >= size )
            throw new IllegalArgumentException("the index is illegal,set is fail");

        Node node = dummyHead.next;

        for (int i = 0 ; i < index ; i++ ){
            node = node.next;
        }
        node.e = e;
    }

    @Override
    public boolean contains(E e) {

        Node node = dummyHead.next;
        for (int i = 0 ; i < size-1; i++){
            if (node.e == e)
                return true;
            node = node.next;
        }

      return false;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }



    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();

        Node node = dummyHead.next;

        while (node != null){
            res.append(node.e+"->");
            node = node.next;
        }

        res.append("NULL");

        return res.toString();
    }
}

测试

public class Main {

    public static void main(String[] args) {
       LinkedList<Integer> list = new LinkedListImpl<>();

       for (int i = 0 ; i < 10 ; i++){
           list.add(i,i);
           System.out.println(list);

       }
        list.removeFirst();
        System.out.println(list);

        list.removeLast();
        System.out.println(list);

        System.out.println(list.get(2));

        System.out.println(list.isEmpty());

        System.out.println(list.size());


    }
}

结果

image.png