Java构建单向链表

链表分为单向链表和双向链表，本文分享Java如何构建单向链表。

单向链表数据结构

单向链表的每一个节点都有两块区域，一个区域放着当前节点的值，另一个区域指向下一个节点，数据结构如下

按照此图示，代码实例展示了一个只有初步构建功能的单向链表

基础构建代码

/**
 * 单向链表构建
 * @param <T>
 */
public class Linked<T> {

    /**
     * 链表节点的构建
     */
    public class Node{
        private Node next;
        private T t;

        public Node(T t, Node next){
            this.t = t;
            this.next = next;
        }

        public Node(T t){
            this(t, null);
        }

        public Node(){

        }

        /**
         * 获取当前节点的值
         * @return
         */
        public T get(){
            return t;
        }
      
      	/**
         * 修改当前节点的值
         */
        public void set(T t){
            this.t = t;
        }
    }

    private Node head;
    private int size;

    /**
     * 默认链表构造函数
     */
    public Linked(){
        this.head = null;
        this.size = 0;
    }
}

链表节点增加

链表的增加要利用next转变指向，即在增加的位置，增加节点的前一个节点的next指向增加节点，增加节点的next指向增加节点后一个节点，这样就完成了指向的转变，实现链表的增加

示例代码

/**
 * 增加一个头节点
 * @param t
 */
public void addFirst(T t){
    Node node = new Node(t);
    node.next = this.head;
    this.head = node;
    this.size++;
}

/**
 * 增加一个尾节点
 * @param t
 */
public void addLast(T t){
    add(t, this.size);
}

/**
 * 根据index增加一个节点，如index=1，即增加第二个节点为...
 * @param t
 * @param index
 */
public void add(T t, int index){
    if(index < 0 || index > this.size){
        throw new IllegalArgumentException("index is error");
    }

    if(index == 0){
        addFirst(t);
        return;
    }

    Node prevNode = this.head;
    for(int i=0; i<index-1; i++){
        prevNode = prevNode.next;
    }

    Node newNode = new Node(t);
    newNode.next = prevNode.next;
    prevNode.next = newNode;

    this.size++;
}

链表节点删除

单向链表的删除与增加正好相反，被删除节点的前一个节点的next，指向被删除节点的后一个节点即可完成删除操作

示例代码

/**
 * 删除头节点
 */
public void deleteFirstNode(){
    if(this.head == null){
        System.out.println("没有元素可以删除");
    }
    this.head = head.next;
    this.size--;
}

/**
 * 删除尾节点
 */
public void deleteLastNode(){
    if(this.head == null){
        System.out.println("没有元素可以删除");
    }
    Node temp = this.head;
    while(temp.next != null){
        temp = temp.next;
    }

    temp.next = null;
    this.size--;
}

/**
 * 根据index删除节点
 * @param index
 */
public void delete(int index){
    if(index < 0 || index > this.size){
        throw new IllegalArgumentException("index超限或小于0");
    }

    if(index == 0){
        this.deleteFirstNode();
        return;
    }else if(index == this.size-1){
        this.deleteLastNode();
        return;
    }else{
        Node prev = this.head;
        Node temp = this.head;

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

        prev.next = temp.next;
        this.size--;
    }
}

已知节点的情况下，删除本节点

这是剑指Offer的一个链表题目，要求在已知节点是什么的情况下，删除本节点，要求时间复杂度为O(1)；在未知节点，或者只知道index的情况下，我们肯定要从头开始循环找到相应的节点，然后操作被删除节点的前一个节点的next来完成删除操作，但在已知节点的情况下，可以换个思路

在已知节点的情况，我们也就能知道已知节点的下一个节点是什么，那么我们可以让已知节点的值等于下一个节点的值，已知节点的next等于下一个节点的next，这样就相当于跳过了已知节点，实现删除操作

实例代码

/**
 * 给定一个节点，按时间复杂度O(1)删除本节点
 * @param node
 */
public void deleteByNode(Node node){

    if(node.next == null){
        Node temp = this.head;
        while(temp.next != node){
            temp = temp.next;
        }
        temp.next = null;
    }else if(node == head){
        this.head = head.next;
    }else{
        node.t = node.next.t;
        node.next = node.next.next;
    }

    this.size--;
}

链表节点修改

链表节点的修改这里给出的是修改值，简单的使用构造函数就可以了，如果是要修改节点的next，那实际上和删除没什么区别，这里不再给出实例代码

示例代码

/**
 * 根据index修改节点的值
 * @param t
 * @param index
 */
public void update(T t, int index){
    if(index < 0 || index > this.size){
        throw new IllegalArgumentException("index超限或小于0");
    }

    if(index == 0){
        this.updateFirstNode(t);
        return;
    }else if(index == this.size-1){
        this.updateLastNode(t);
        return;
    }else{
        Node temp = this.head;

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

        //temp.set(t); 这个也可以
        temp.t = t;
    }
}

/**
 * 修改头结点的值
 * @param t
 */
public void updateFirstNode(T t){
    //this.head.set(t); 这个也可以
    this.head.t = t;
}

/**
 * 修改尾节点的值
 * @param t
 */
public void updateLastNode(T t){
    Node temp = this.head;

    for(int i=0; i<this.size-1; i++){
        temp = temp.next;
    }

    //temp.set(t); 这个也可以
    temp.t = t;
}

因为Node的方法中暴露的一个set，且为public，所以在使用这个链表的时候，也可以获得节点后通过set方法修改节点的值

实例代码

public static void main(String[] args){
    Linked<String> linked = new Linked<>();

    linked.addFirst("no1");
    linked.addLast("no2");
    linked.addLast("no3");
    linked.addLast("no4");
    linked.addLast("no5");
    linked.addLast("no6");
    linked.addLast("no7");
    linked.addLast("no8");

    //可以将 no4 修改为 all
    linked.getNode(3).set("all");
}

链表节点查看

链表节点的查询这里给出的方法是获取节点，和update的方法类似，将最后的return temp改成return temp.t即可返回节点的值，在这里给出的实例代码需要再使用时使用Node类暴露的get()方法

示例代码

/**
 * 根据index获取节点
 * @param index
 * @return
 */
public Node getNode(int index){
    if(index < 0 || index > this.size){
        throw new IllegalArgumentException("index超限或小于0");
    }

    if(index == 0){
        return this.getFirstNode();
    }else if(index == this.size-1){
        return this.getLastNode();
    }else{
        Node temp = this.head;

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

        return temp;
    }
}

/**
 * 获取尾节点
 * @return
 */
public Node getLastNode(){
    Node temp = this.head;

    for(int i=0; i<this.size-1; i++){
        temp = temp.next;
    }

    return temp;
}

/**
 * 获取头节点
 * @return
 */
public Node getFirstNode(){
    return this.head;
}

获取链表长度

链表类里面维护了一个size，在delete操作时会减1，add操作时会加1，所以可以直接返回这个size

示例代码

/**
 * 获取链表长度
 * @return
 */
public int getSize(){
    return this.size;
}

整体Linked类示例代码

/**
 * 单向链表构建
 * @param <T>
 */
public class Linked<T> {

    /**
     * 链表节点的构建
     */
    public class Node{
        private Node next;
        private T t;

        public Node(T t, Node next){
            this.t = t;
            this.next = next;
        }

        public Node(T t){
            this(t, null);
        }

        public Node(){

        }

        /**
         * 获取当前节点的值
         * @return
         */
        public T get(){
            return t;
        }

        /**
         * 修改当前节点的值
         */
        public void set(T t){
            this.t = t;
        }
    }

    private Node head;
    private int size;

    /**
     * 默认链表构造函数
     */
    public Linked(){
        this.head = null;
        this.size = 0;
    }

    /**
     * 增加一个头节点
     * @param t
     */
    public void addFirst(T t){
        Node node = new Node(t);
        node.next = this.head;
        this.head = node;
        this.size++;
    }

    /**
     * 增加一个尾节点
     * @param t
     */
    public void addLast(T t){
        add(t, this.size);
    }

    /**
     * 根据index增加一个节点
     * @param t
     * @param index
     */
    public void add(T t, int index){
        if(index < 0 || index > this.size){
            throw new IllegalArgumentException("index is error");
        }

        if(index == 0){
            addFirst(t);
            return;
        }

        Node prevNode = this.head;
        for(int i=0; i<index-1; i++){
            prevNode = prevNode.next;
        }

        Node newNode = new Node(t);
        newNode.next = prevNode.next;
        prevNode.next = newNode;

        this.size++;
    }

    /**
     * 给定一个节点，按时间复杂度O(1)删除本节点
     * @param node
     */
    public void deleteByNode(Node node){

        if(node.next == null){
            Node temp = this.head;
            while(temp.next != node){
                temp = temp.next;
            }
            temp.next = null;
        }else if(node == head){
            this.head = head.next;
        }else{
            node.t = node.next.t;
            node.next = node.next.next;
        }

        this.size--;
    }

    /**
     * 删除头节点
     */
    public void deleteFirstNode(){
        if(this.head == null){
            System.out.println("没有元素可以删除");
        }
        this.head = head.next;
        this.size--;
    }

    /**
     * 删除尾节点
     */
    public void deleteLastNode(){
        if(this.head == null){
            System.out.println("没有元素可以删除");
        }
        Node temp = this.head;
        Node newTemp = temp;
        while(temp.next != null){
            newTemp = temp;
            temp = temp.next;
        }

        newTemp.next = null;
        this.size--;
    }

    /**
     * 根据index删除节点
     * @param index
     */
    public void delete(int index){
        if(index < 0 || index > this.size){
            throw new IllegalArgumentException("index超限或小于0");
        }

        if(index == 0){
            this.deleteFirstNode();
            return;
        }else if(index == this.size-1){
            this.deleteLastNode();
            return;
        }else{
            Node prev = this.head;
            Node temp = this.head;

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

            prev.next = temp.next;
            this.size--;
        }
    }

    /**
     * 根据index修改节点的值
     * @param t
     * @param index
     */
    public void update(T t, int index){
        if(index < 0 || index > this.size){
            throw new IllegalArgumentException("index超限或小于0");
        }

        if(index == 0){
            this.updateFirstNode(t);
            return;
        }else if(index == this.size-1){
            this.updateLastNode(t);
            return;
        }else{
            Node temp = this.head;

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

            //temp.set(t); 这个也可以
            temp.t = t;
        }
    }

    /**
     * 修改头结点的值
     * @param t
     */
    public void updateFirstNode(T t){

        //this.head.set(t); 这个也可以
        this.head.t = t;
    }

    /**
     * 修改尾节点的值
     * @param t
     */
    public void updateLastNode(T t){
        Node temp = this.head;

        for(int i=0; i<this.size-1; i++){
            temp = temp.next;
        }

        //temp.set(t); 这个也可以
        temp.t = t;
    }

    /**
     * 根据index获取节点
     * @param index
     * @return
     */
    public Node getNode(int index){
        if(index < 0 || index > this.size){
            throw new IllegalArgumentException("index超限或小于0");
        }

        if(index == 0){
            return this.getFirstNode();
        }else if(index == this.size-1){
            return this.getLastNode();
        }else{
            Node temp = this.head;

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

            return temp;
        }
    }

    /**
     * 获取尾节点
     * @return
     */
    public Node getLastNode(){
        Node temp = this.head;

        for(int i=0; i<this.size-1; i++){
            temp = temp.next;
        }

        return temp;
    }

    /**
     * 获取头节点
     * @return
     */
    public Node getFirstNode(){
        return this.head;
    }

    /**
     * 获取链表长度
     * @return
     */
    public int getSize(){
        return this.size;
    }

}