Java自定义实现单链表

目录

一、自定义java单链表原理概述

二、自定义java单链表功能实现细节

三、实现代码

        1、单链表概念

                单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点（node）来表示的，每个结点的构成是由元素 +指针(指示后继元素的存储位置)，元素就是存储数据的存储单元，指针就是指向下一个节点的地址。

        2、单链表的特点及复杂度分析

                单链表无法像数组一样能够随机访问某个节点，只能从表头向下逐个遍历至目标节点（复杂度为O(n)）；单链表的增删操作都仅需要修改节点的next来达到目的，所以时间复杂度均为O(1)，效率高，但是链表的元素的添加存在new操作，当操作规模庞大时，单链表的性能是会受到影响的，对于内存的消耗较大，效率反而会降低（可对比于上一篇——自定义动态数组）。

        3、Node结构示意图

        4、Node示意图解析

                如上图所示，我们定义一个Node类，在该类中定义两个成员变量分别为value和next，其中value为该节点的值，泛型化以满足用户更丰富的需求；next为下一个节点（引用/指针），到此，有些人会产生疑问，为什么传统概念上说next是下一节点的指针，这里为什么还要用Node类型呢？指针又将放在哪呢？

                对此，是因为我们忽略了一个最普遍的概念， 那就是对于java的单链表来说，它是区别于C/C++语言的，一般来说java中的对象存在于内存中（有可能存在于栈中——逃逸分析），对应着内存中的唯一一个地址，也就是指针。所以next就相当于是递归调用了Node的构造函数，存放了该节点的下一个节点，简单来说：next对象就相当于是下一个节点的引用。

        5、单链表的应用

                常见应用于InnoDB存储引擎中的pageB+树叶子节点中，叶子节点中的数据为单链表（节点之间为双向链表）、LRU cache。

二、自定义java单链表功能实现细节

        1、虚拟头结点VirtualNode

                 如上图，在自定义单链表LinkedList类中，设置了两个成员变量，size表示链表的长度；virtualHead为链表的虚拟头结点；

                虚拟头结点的作用是为链表预设一个逻辑上的头结点，实质该节点是并不存在的，此时链表的size还是为0的，这仅仅是为了使链表的实现逻辑通顺易懂。在设置虚拟头结点后，此时链表中的每一个节点都有一个前趋节点；将虚拟节点设置为链表的第一个节点，当链表为空时，在此基础上，再进行添加新节点的操作时，便可直接将该虚拟节点的next设为要添加的新节点，即对virtualHead节点的next进行赋值操作与size++即可；同理在删除、遍历，获取对应位置节点值等操作中，头结点便同其他节点一样，不再具有特殊性，没有虚拟头结点的特殊之处是因为在没有虚拟头结点时对于单链表元素的操作都是通过对目标节点的前一个节点的next进行管理，而头结点并没有前一个节点，这时就需要进行特殊处理。

        2、对于LinkedList的封装，是将Node类作为LinkedList的一个内部类，并不独立出来为一个Node类，这是因为对于使用者来说，Node类的意义不大，用户只需要通过LinkedList类创建一个单链表，然后进行RUD等操作即可，这也是对类封装性的加强。

        3、功能概览

三、实现代码

package custom.linked;


public class LinkedList {
    
    private class Node {
        public E value;
        public Node next;

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

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

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

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }

    private Node virtualHead;//虚拟头结点
    private int size;//链表长度

    
    public LinkedList() {
        virtualHead = new Node();
        size = 0;
    }

    
    public int getSize() {
        return size;
    }

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

    
    public boolean addBetweenIndex(int previousIndex, int afterIndex, E element) {
        if (previousIndex < 0 || afterIndex < 0) {
            throw new IllegalArgumentException("index out of bounds,the arg is illegal!");
        }
        if (previousIndex > size || previousIndex > size - 1) {
            throw new IllegalArgumentException("index out of bounds,the arg is illegal!");
        }
        if (size < 2) {
            throw new RuntimeException("method is not suit your demand!");
        }
        Node previousNode = virtualHead;//从头结点开始，遍历搜索至preciousIndex处的节点
        for (int i = 0; i < afterIndex; i++) {
            previousNode = previousNode.next;
        }
        
        previousNode.next = new Node(element, previousNode.next);
        size++;
        return true;
    }

    
    public boolean addFirst(E element) {
        Node previousNode = virtualHead;
        previousNode.next = new Node(element, previousNode.next);
        size++;
        return true;
    }

    
    public boolean addLast(E element) {
        Node previousNode = virtualHead;
        if (size == 0) {
            previousNode = virtualHead;
            previousNode.next = new Node(element, null);
            size++;
            return true;
        }
        for (int i = 0; i < size; i++) {
            previousNode = previousNode.next;
        }
        previousNode.next = new Node(element, null);
        size++;
        return true;
    }

    
    public E deleteIndexNode(int index) {
        if (index < 0 || index > size - 1) {
            throw new IllegalArgumentException("the index is illegal!");
        }
        if (index == 0) {
            deleteHeadNode();
        }
        if (index == size - 1) {
            deleteLastNode();
        }
        Node previousNode = virtualHead;
        for (int i = 0; i < index; i++) {
            previousNode = previousNode.next;
        }
        E deleteElement = previousNode.next.value;
        previousNode.next = previousNode.next.next;
        size--;
        return deleteElement;
    }

    
    public E deleteHeadNode() {
        Node previousNode = virtualHead;
        E deleteElement = previousNode.next.value;
        previousNode.next = previousNode.next.next;
        size--;
        return deleteElement;
    }

    
    public E deleteLastNode() {
        Node previousNode = virtualHead;
        for (int i = 0; i < size - 1; i++) {
            previousNode = previousNode.next;
        }
        E deleteElement = previousNode.next.value;
        previousNode.next = null;
        size--;
        return deleteElement;
    }

    
    public E getIndexElement(int index) {
        Node previousNode = virtualHead;
        for (int i = 0; i < index; i++) {
            previousNode = previousNode.next;
        }
        return previousNode.next.value;
    }

    
    public void traverseList() {
        Node previousNode = virtualHead;
        for (int i = 0; i < size; i++) {
            previousNode = previousNode.next;
            System.out.println(previousNode.value);
        }
    }

    
    public LinkedList reversed() {
        LinkedList newList = new LinkedList();//存放反转后的链表
        for (int i = 0; i < size; i++) {
            newList.addFirst(getIndexElement(i));
        }
        return newList;
    }

    
    public E[] toArray() {
        E[] array = (E[]) new Object[size];
        for (int i = 0; i < size; i++) {
            array[i] = getIndexElement(i);
        }
        return array;
    }

    
    public LinkedList constructorLinkedList(E[] array) {
        if (!isEmpty()) {
            throw new RuntimeException("LinkedList is must be empty!");
        }
        for (int i = 0; i < array.length; i++) {
            addLast(array[i]);
        }
        return this;
    }
}