java实现链表

1、什么是链表

链表是一种数据结构，和数组同级别。Java中我们使用的LInkedList，其实现原理为链表，而ArrayList其实现原理为数组。链表在插入和删除时优势明显。

单链表是一种线性表，实际上由节点（Node）组成，可以把单链表想象成为一列火车，而组成单链表的每个节点想象成为一节车厢。节点中存储了节点的值（data）以及指向下一个节点的指针（Next）。

2、单链表的实现（增删查改）

package LinkedList;
 
// 车厢类
class Node {
 
    // 存储具体元素
    int data;
    // 存储下一个结点地址(钩子)
    Node next;
 
    public Node(int data) {
        this.data = data;
    }
 
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}
 
 
// 火车
public class SingleLinkedList {
 
    // 当前火车中车厢的个数(实际存储的元素个数)
    private int size;
    // 当前火车的第一个结点
    private Node head;
    // 在火车头部添加元素
    public void addFirst(int data) {
        // 要使用addFirst向火车中添加结点，要判断当前火车是否为空
        // -> 一个结点都没有
        // 要插入的结点就是第一个结点
        if(size == 0) {
            Node node = new Node(data);
            head = node;
            size ++;
        }else {
            // 当前火车已经存在结点了
            Node node = new Node(data);
            node.next = head;
            head = node;
            size ++;
        }
    }
 
    public void addIndex(int index,int data) {
        // 一定注意边界条件
        // 判断index的合法性
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        // 若index = 0;
        if (index == 0) {
            // 链表的头部节点插入
            addFirst(data);
            return;
        }
        // 说明此时index合法且在中间位置(包含最后节点)
        // 此时需要找到待插入位置index的前驱节点
        // 单链表中只能从前到后遍历
        Node node = new Node(data);
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        // prev引用指向当前插入index的前驱
        node.next = prev.next;
        prev.next = node;
        size ++;
    }
 
    public void addLast(int data) {
        addIndex(size,data);
    }
 
    /**
     * 查询index位置的节点数据
     * @param index
     * @return 节点数据
     */
    public int get(int index) {
        if (rangeCheck(index)) {
            Node node = head;
            for (int i = 0;i < index;i++) {
                node = node.next;
            }
            // 此时node指向待查找元素的索引
            int data = node.data;
            return data;
        }else {
            System.err.println("get index illegal!");
            return -1;
        }
    }
 
    /**
     * 修改单链表中index位置的元素
     * 返回修改前的元素值
     * @param index
     * @param data
     * @return
     */
    public int set(int index,int data) {
        if (rangeCheck(index)) {
            // 需要找到index位置的节点
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            int oldData = node.data;
            node.data = data;
            return oldData;
        }else {
            System.err.println("set index illegal!");
            return -1;
        }
    }
 
    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }
 
    /**
     * 判断单链表中是否包含元素data
     * @param data
     * @return
     */
    public boolean contains(int data) {
        Node node = head;
        while (node != null) {
            if (node.data == data) {
                System.out.println("找到元素！");
                return true;
            }
            node = node.next;
        }
        System.out.println("没有找到该元素");
        return false;
    }
 
    public void removeFirst() {
        Node node = head;
        head = head.next;
        node.next = null;
        size --;
    }
 
    public void removeIndex(int index) {
        // 判断边界条件
        if (rangeCheck(index)) {
            if (index == 0) {
                // 此时删除头节点
                removeFirst();
            }else {
                // 此时index删除的中间位置节点
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                // prev指向待删除节点的前驱节点
                // node就是待删除的节点
                Node node = prev.next;
                // 链接前驱节点和后继节点
                prev.next = node.next;
                // 将当前节点的next引用置为空，脱钩操作
                node.next = null;
                size --;
            }
        }else {
            System.err.println("remove index illegal!");
        }
    }
 
    /**
     * 删除链表中指定元素的第一个节点
     * @param data
     */
    public void removeValueOnce(int data) {
        // 先要找到待删除的元素的节点
        // 先判断头节点的情况
        if (head.data == data) {
            // 此时头节点就是第一个待删除的节点
            removeFirst();
        }else {
            // 此时头节点一定不是要删除的节点
            // 从头节点开始找到待删除的节点前驱
            Node prev = head;
            // 此时要看下一个节点的情况
            while (prev.next != null) {
                // 找到待删除的节点
                if (prev.next.data == data) {
                    // 此时perv就是待删除节点的前驱
                    // node节点就是待删除的节点
                    Node node = prev.next;
                    // 将prev跳过当前node
                    prev.next = node.next;
                    node.next = null;
                    size --;
                    break;
                }else {
                    // 此时prev的下一个节点不是待删除的节点
                    // 继续向下一个节点前进
                    prev = prev.next;
                }
            }
        }
    }
 
    public void removeAllValue(int data) {
        // 判断头节点的情况
        // 头节点以及之后出现了多个连续待删除的节点
        while (head != null && head.data == data) {
            Node node = head;
            head = head.next;
            node.next = null;
            size --;
        }
        // 此时head一定不是待删除的节点
        // head.data != data
        if (head == null) {
            // 此时链表全部是待删除的节点，全部删除完毕
            return;
        }else {
            // 此时头节点已经处理完毕，并且链表也不为空，向下一个节点开始判断
            Node prev = head;
            while (prev.next != null) {
                if (prev.next.data == data) {
                    // node就是待删除的节点
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size --;
                }else {
                    // 此时prev的下一个节点不是要删除的节点，prev继续向后走一个单位
                    prev = prev.next;
                }
            }
        }
    }
 
 
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(3);
        singleLinkedList.addLast(2);
        System.out.println(singleLinkedList);
        singleLinkedList.removeAllValue(2);
        // 3
        System.out.println(singleLinkedList);
    }
 
    @Override
    public String toString() {
        String ret = "";
        // 为啥此时要有一个临时变量node来存储head的值?
        Node node = head;
        while (node != null) {
            ret += node.data + "->";
            // 继续访问下一节车厢
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}

3、链表顺序表（数组）的比较

        ①空间资源分配

                数组：数组又叫做顺序表，顺序表是在内存上开辟一段连续的空间来存储数据，数组不允许动态定义数组大大小，即只能在数组定义的时候确定数组的大小。而在实际的使用过程中，用户也无法确定数组的大小，往往出现两种情况：分配的空间太小，数组不够用；分配的空间太大，造成内存空间浪费。

                链表：链表可以看成一列小火车，其由一节节车厢相连而成，物理上是不连续的，逻辑上连续，链表进行动态内存分配，可以适应数据动态的增减的情况。需要新的数据，就new一个节点出来，与原链表相连，不需要时则进行删除，空间释放，不会造成空间的浪费。

        ②表操作时间复杂度

                数组：数组就像编了号站成一排的人，查找某个位置的人很容易，直接根据编号进行查找O(1),而若是进行删除和插入操作就很复杂，后面的人身上的编号都要发生变化O(n)。

                链表：链表就像一列火车，查找某节车厢，需要从前往后遍历O(n)，比较复杂，而插入和删除则只需要进行脱钩和连钩操作O(1)。