[数据结构与算法]Java数据结构之链表（单链表）

一、链表

概念

链表：逻辑上连续，多个节点采用挂载式进行连接。但是物理上非连续存储结构。（火车）

结构：从头开始遍历，一直到达尾部。
火车：当数据空间不够时，就新增一节车厢挂载到火车尾。

结构

链表的结构十分多样，以下条件组合起来会有8种链表结构：
??①单向、双向
??②带头、不带头
??③循环、非循环
重点掌握其中两种：
??①无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
??②无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

回到目录…

二、无头单链表

图解

单向遍历，默认从前向后遍历。只能从头部车厢开始遍历，依次走到尾部。

代码实现

/*火车车厢类，一个车厢只能存放一个元素*/
public class Node {
    //存放具体数据
    int value;
    //保存下一个车厢的地址
    Node next;
    public Node(int value){ this.value = value;}
}

/**
 * 火车类，是由多个车厢连接起来的
 */
public class SingleLinkedList {
    //当前火车中车厢节点的个数(实际就是元素的个数)
    private int size;
    //当前火车的头车厢地址
    private Node head;

    /****  添加  *********************/
    //头插法
    public void addFirst(int value){
        //新建一个车厢节点
        Node node = new Node(value);
        //先判断当前火车是否为空
        if(head == null){
            head = node;
        }else{
            //火车头有节点，要把当前新车厢挂载到火车头部
            //先把原本的头部车厢指向新车厢的下一节
            node.next = head;
            //再将这个新增的车厢node指向头部head
            head = node;
        }
        size++;
    }
    //索引插入
    public void addIndex(int index,int value){
        //先判断是否索引越界
        if(index<0||index>size){
            System.err.println("add index illegal!");
            return;
        }
        //index==0，说明是头插
        if(index == 0){
            addFirst(value);
            return;
        }
        //创建一个新的车厢
        Node node = new Node(value);
        //建一个prev，寻找插入位置的前驱,从头节点开始向后走index-1步
        Node prev = head;
        for(int i=0;i<index-1;i++){
            prev = prev.next;
        }
        //node的下一节指向前驱temp的下一节
        node.next = prev.next;
        //前驱的下一节指向node
        prev.next = node;
        size++;
    }
    //尾插
    public void addLast(int value){
        addIndex(size,value);
    }

    /****  查找  *********************/
    //返回索引处value的值
    public int get(int index){
        if(rangeCheck(index)){
            //从头节点开始，走到index的位置
            Node node = head;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            return node.value;
        }else{
            System.err.println("get index illegal!");
            return -1;
        }
    }
    //判断链表中是否有value这个数据、
    public boolean contains(int value){
        for(Node temp=head;temp!=null;temp=temp.next){
            if(temp.value == value)
                return true;
        }
        return false;
    }

    /****  修改  *********************/
    //将单链表中索引为index的元素修改，并返回修改前的值
    public int set(int index,int value){
        if(rangeCheck(index)){
            Node node = head;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            int old = node.value;
            node.value = value;
            return old;
        }else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

    /****  删除  *********************/
    //删除索引处的数据
    public void removeIndex(int index){
        if(rangeCheck(index)){
            if(index == 0){
                Node temp = head;
                head = head.next;
                temp.next = null;
                size--;
            }else{
                //找到待删除节点的前驱
                Node prev = head;
                for(int i=0;i<index-1;i++){
                    prev = prev.next;
                }
                //cur表示待删除节点
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
            }
        }else{
            System.err.println("remove index illegal!");
        }
    }
    //删除单链表中的第一个value值
    public void removeOnceValue(int value){
        //遍历链表，找到value的节点的前驱
        //头节点没有前驱，要特殊处理
        if(head!=null && head.value == value){
            removeIndex(0);
            return;
        }
        //找待删节点的前驱，该前驱的下一节点就是value
        Node prev = head;
        while(prev.next != null){
            if(prev.next.value == value){
                //cur就是待删节点
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
                return;
            }
            //prev不是待删节点的前驱，让prev继续向后走
            prev = prev.next;
        }
    }
    //删除单链表中的全部value值
    public void removeAllValue(int value){
        //判断头节点是否为待删除节点
        while(head!=null && head.value==value){
            head = head.next;
            size--;
        }
        if(head == null){
            //说明链表中全是待删节点，此时链表被删空
            return;
        }else{
            //此时head一定不是待删节点,再看链表中的其它节点
            Node prev = head;
            while(prev.next != null){
                if(prev.next.value == value){
                    //cur就是待删节点
                    Node cur = prev.next;
                    prev.next = cur.next;
                    cur.next = null;
                    size--;
                }else{
                    //只有确保prev的下一个不是待删节点，才让prev继续向后走一步
                    prev = prev.next;
                }
            }
        }
    }

    //打印
    public String toString(){
        String str = "";
        //遍历这个火车类，从头部(head)走到尾部
        //暂时存储头节点地址，避免遍历结束影响head的值
        Node node = head;
        while(node != null){
            str += node.value;
            str += " -> ";
            //当前地址指向下一节车厢的地址
            node = node.next;
        }
        str += "NULL";
        return str;
    }

    //判断 查、改、删操作时，索引是否越界
    private boolean rangeCheck(int index){
        if(index<0||index>=size)
            return false;
        else
            return true;
    }
}

特点

1.每次增、删操作时，都要改动size的值
2.每当对head进行操作时，必须先考虑head是否为空. (防止空指针异常)
3.进行查、改、删操作时，需要判断用户输入的索引是否越界[0,size)
4.在进行索引插入和删除操作时，都需要找前驱节点。(但是头节点没有前驱，所以要特殊处理)

回到目录…

三、带头单链表

为何引入带头单链表

?因为初学的单链表每次插入和删除元素时，都需要找前驱；此时需要特殊处理头节点。(因为头节点没有前驱)
?为了避免这一步繁琐的操作，将所有节点都一视同仁 ——> 不用处理头节点 ——> 虚拟头节点(这个节点仅仅作为链表的头部，不储存具体元素) ——> 火车头不坐乘客

代码实现

/**
 * 带头单链表
 */
public class SingleLinkedListWithHead {
    //表示当前链表中元素的个数
    private int size;
    //创建虚拟头节点
    private Node dummyHead = new Node(-1);

    /****  添加  *********************/
    public void addIndex(int index,int value){
        //判断index合法性
        if(index<0 || index>size){
            System.err.println("add index illegal!");
            return;
        }
        //此时的插入就不可能是头插
        Node node = new Node(value);
        //找到插入位置的前驱
        Node prev = dummyHead;
        for(int i=0;i<index;i++){
            //因为链表的头部有个虚拟节点，所以要走index步才行
            prev = prev.next;
        }
        //此时prev指向待插位置的前驱
        node.next = prev.next;
        prev.next = node;
        size++;
    }
    public void addFirst(int value){
        addIndex(0,value);
    }
    public void addLast(int value){
        addIndex(size,value);
    }

    /****  查找  *********************/
    //返回索引处value的值
    public int get(int index){
        if(rangeCheck(index)){
            Node node = dummyHead.next;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            return node.value;
        }else{
            System.err.println("get index illegal!");
            return -1;
        }
    }
    //判断链表中是否有value这个数据
    public boolean contains(int value){
        for(Node temp=dummyHead.next;temp!=null;temp=temp.next){
            if(temp.value == value)
                return true;
        }
        return false;
    }

    /****  修改  *********************/
    //将单链表中索引为index的元素修改，并返回修改前的值
    public int set(int index,int value){
        if(rangeCheck(index)){
            Node node = dummyHead.next;
            for(int i=0;i<index;i++){
                node = node.next;
            }
            int old = node.value;
            node.value = value;
            return old;
        }else{
            System.err.println("set index illegal!");
            return -1;
        }
    }

    /****  删除  *********************/
    public void removeIndex(int index){
        if(rangeCheck(index)){
            Node prev = dummyHead;
            for(int i=0;i<index;i++){
                prev = prev.next;
            }
            Node cur = prev.next;
            prev.next = cur.next;
            cur.next = null;
            size--;
        }else{
            System.err.println("remove index illegal!");
        }
    }
    public void removeOnceValue(int value){
        Node prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.value == value){
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
                return;
            }
            prev = prev.next;
        }
    }
    public void removeAllValue(int value){
        Node prev = dummyHead;
        while(prev.next!=null){
            if(prev.next.value == value){
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
            }else{
                prev = prev.next;
            }
        }
    }

    public String toString(){
        String str = "";
        Node temp = dummyHead.next;
        while(temp!=null){
            str += temp.value;
            str += " -> ";
            temp = temp.next;
        }
        str += "NULL";
        return str;
    }

    private boolean rangeCheck(int index){
        if(index<0 || index>=size)
            return false;
        else
            return true;
    }

    public int size(){
        return this.size;
    }
}

注意

1.虚拟头节点的值最好取value范围之外的值。Node dummyHead = new Node(value:-1);
2.dummyHead只是虚假的节点，进行查、改操作时，要避开它，从它的下一个节点开始遍历。

回到目录…

总结:
提示：这里对文章进行总结：
以上就是今天的学习内容，本文是Java数据结构的链表部分，介绍了链表的实现原理，以及带头单链表的引入。之后的学习内容将持续更新！！！