自定义一个LinkedList

LinkedList特点和底层实现

LinkedList底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。

双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。下图为LinkedList的存储结构图：

每个节点都应该有3部分内容：

class  Node {
        Node  previous;     //前一个节点
        Object  element;    //本节点保存的数据
        Node  next;         //后一个节点
}

查看LinkedList的源码，可以看到里面包含了双向链表的相关代码：

自定义一个LinkedList，体会底层原理

代码如下：

package com.msl.mycollection;
/**
 * 自定义实现一个链表
 * @author Senley
 */
public class MslLinkedList<E> {

    private Node first;
    private Node last;
    private int size;

    public static void main(String[] args) {
        MslLinkedList<String> list = new MslLinkedList();
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);
        System.out.println(list.get(2));
        list.remove(0);
        System.out.println(list);
        list.add(1, "插入");
        System.out.println(list);
    }

    public void add(int index,E element) {
        checkRange(index);
        Node newNode = new Node(element);
        Node temp = getNode(index);
        if(temp!=null) {
            Node up = temp.previous;
            up.next = newNode;
            newNode.previous = up;
            newNode.next = temp;
            temp.previous = newNode;
        }
    }

    public void remove(int index) {
        checkRange(index);
        Node temp = getNode(index);
        if(temp!=null) {
            Node up = temp.previous;
            Node down = temp.next;
            if(up!=null) {
                up.next = down;
            }
            if(down!=null) {
                down.previous = up;
            }
            //被删除的元素是第一个元素时
            if(index==0) {
                first = down;
            }
            //被删除的元素是最后一个元素时
            if(index==size-1) {
                last = up;
            }
            size--;
        }
    }

    public void add(E element) {
        Node node = new Node(element);
        if(first==null) {
//          node.previous = null;
//          node.next = null;
            first = node;
            last = node;
        }else {
            node.previous = last;
            node.next = null;
            last.next = node;
            last = node;
        }
        size++;
    }

    public E get(int index) {
        checkRange(index);
        Node temp = getNode(index);
        return temp!=null?(E)temp.element:null;
    }

    private void checkRange(int index) {
        if(index<0 || index>size-1) {
            throw new RuntimeException("索引数字不合法:"+index);
        }
    }

    private Node getNode(int index) {
        checkRange(index);
        Node temp = null;
        if(index<=(size>>1)) {//size>>1相当于除以2
            temp = first;
            for(int i=0;i<index;i++) {
                temp = temp.next;
            }
        }else {
            temp = last;
            for(int i=size-1;i>index;i--) {
                temp = temp.previous;
            }
        } 
        return temp;
    }

    @Override
    public String toString() {
        //[a b c] first = a, last = c
        StringBuilder sb = new StringBuilder("[");
        Node temp = first;
        while(temp!=null) {
            sb.append(temp.element+",");
            temp = temp.next;
        }
        sb.setCharAt(sb.length()-1, ']');
        return sb.toString();
    }

}

结果如下：

[a,b,c]
c
[b,c]
[b,插入,c]