数据结构与算法Java——链表

本文主要是介绍数据结构与算法Java——链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链表

1.单向链表

代码实现：

package 链表;


import java.util.Stack;
/*
* 单向链表
* 由于单链表的单向性，我们在遍历等操作时往往要使用temp.next来先判断一下下个节点的状况，这样是为了在删除等操作时，我们还能得到被删除
* 节点的上一个节点是哪一个，不然我们若直接删除temp,由于单向性我们拿不到其上一个节点了，而因为有next指针所以可以拿到下一个节点。
* 也因此我们专门设置了一个不含信息的头指针作为火车头来起到引导作用，其可以不加，但是加了更容易理解单链表的单向性
* */
public class LinkedList {
    private Node head = new Node(-1,"","");  //头节点
    public int len;  //链表有效长度

    public Node getHead() {
        return head;
    }

    //获得链表实际长度（头节点不包含）
    public int length(){
        Node temp = head;
        if(temp.next==null){
            return 0;
        }

        int count = 0;
        while(true){
            if(temp.next==null){
                break;
            }
            count++;
            temp = temp.next;
        }

        return count;
    }

    //删除指定位置节点
    public void deleteNode(int num){
        Node temp = head;
        while(true){
            if(temp.next==null){
                System.out.println("没找到要删除的节点对应的num！");
                break;
            }
            if(temp.next.num == num){
                Node tempNode = temp.next.next;
                temp.next = tempNode;
                break;
            }
            temp = temp.next;
            len--;
        }
    }

    //更新节点
    public void updateNode(Node node){
        Node temp = head;
        while(true){
            if(temp.next==null){
                System.out.println("没找到要更新的节点对应的num！");
                break;
            }
            if(temp.next.num == node.num){
                node.next = temp.next.next;
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }

    //直接添加节点
    public void addNode(Node node){
        Node temp = head;
        while(true){
            if(temp.next==null){
                break;
            }
            temp = temp.next;
        }

        temp.next = node;
        len++;
    }

    //按照num大小顺序将节点添加到指定位置
    public void addNodeByOrder(Node node){
        Node temp = head;
        boolean flag = false;
        while(true){
            if(temp.next==null){
                temp.next = node;
                len++;
                break;
            }
            if(temp.next.num > node.num){
                Node tempNode = temp.next;
                temp.next = node;
                node.next = tempNode;
                len++;
                break;
            }
            if(temp.next.num == node.num){
                System.out.println("有相同的num,添加失败！");
                break;
            }
            temp = temp.next;
        }
    }

    //展示链表有效节点信息
    public void nodeList(){
        Node temp = head;
        while(true){
            if(temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

    /*
    * 反转单链表
    * 思路：
    * 由于单向性我们无法逆序遍历单链表，所以我们可以正序遍历，即：
    * 首先先创建一个新的头节点，其临时作为反转后的链表的头节点；
    * 接着遍历原链表，遍历到第一个，直接加新头节点后面，遍历到第二个时，将第一个与新头的连接断开，
    * 将第二个加在新头后面，第一个再和第二个连接...
    * */
    public void reverseList(){
        //如果链表是空或者是只含有一个元素，无需反转
        if(head.next==null || head.next.next==null){
            return;
        }
        Node reverseHead = new Node(0,"",""); //临时充当head
        Node cur = head.next; //用来起到遍历作用的指针

        while(cur != null){
            Node next = cur.next;  //将要从原链表拿走的节点的下一个节点位置先保存好
            cur.next = reverseHead.next;  //将新头后面的节点放在要添加过来的节点的后面
            reverseHead.next = cur;  //把要添加过来的节点添加在新头后面
            cur = next;  //cur从新头所在的链表上回去，回到原先的链表上继续遍历
        }

        head.next = reverseHead.next; //因为head不能动！ 所以最后再让老头指向新头指向的反转后的链表即可
    }

    /*
    * 逆序打印单链表
    * 可以直接反转后打印，但是逆序打印单链表没有说让你改变单链表的内部顺序！
    * 所以我们可以直接逆序遍历即可！
    * 但是我们又无法逆序遍历，所以该咋办呢？
    * 我们可以还是正序遍历，只不过将遍历到的节点用 栈 来进行存储；
    * 由于栈是先进后出， 所以在遍历完全后 想将栈内元素 拿出来时刚好为逆序拿出，所以完成了逆序遍历思想！
    * */
    public void reversePrintList(){
        Node cur = head.next;
        if(cur==null){
            System.out.println("此链表为空，");
        }
        Stack<Node> stack = new Stack<>();
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        while(stack.size()>0){
            System.out.println(stack.pop());
        }

    }

}

class TestMain {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.addNodeByOrder(new Node(1,"song","rain"));
        linkedList.addNodeByOrder(new Node(3,"zhang","fly"));
        linkedList.addNodeByOrder(new Node(2,"lu","long"));
        linkedList.nodeList();
        System.out.println("========================");
//        System.out.println(linkedList.len);
//        System.out.println(linkedList.length());
//        linkedList.nodeList();
//        System.out.println("============================================");
//        System.out.println(getNodeByBackAndK(linkedList,2));


//        linkedList.reverseList();
//        linkedList.nodeList();
        linkedList.reversePrintList();

    }

    //获得单链表倒数第k个节点
    public static Node getNodeByBackAndK(LinkedList linkedList,int k){
        int n = linkedList.length();

        Node temp = linkedList.getHead();
        if(temp.next==null){
            System.out.println("链表为空");
            return null;
        }
        for(int i=0;i <= n-k;i++){
            temp = temp.next;
        }

        return temp;

    }
}



class Node{
    int num;
    String name;
    String nickname;
    Node next;

    public Node(int num, String name, String nickname) {
        this.num = num;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

2.双向链表

代码实现：

package 链表;
/*
* 双向链表
*
* */
public class DoubleLinkedList {
    private PreNextNode head = new PreNextNode(-1,"","");  //头指针

    //删除指定序号的节点
    public void deleteNode(int num){
        PreNextNode temp = head.next;  //帮助遍历的指针
        /*因为temp是双向的，所以我们不用像单链表那样删一个节点要先拿其上一个节点了，
         因为我们是可以直接定位到要删除的节点的上一个节点从而来更改指向的*/
        while(true){
            if(temp==null){
                System.out.println("没找到num对应的节点！");
                break;
            }
            if(temp.num==num){
                temp.pre.next = temp.next;  //被删除节点的前节点的后节点要指向被删除节点的后节点
                if(temp.next!=null){  //防止空指针，即当删除最后一个节点时
                    temp.next.pre = temp.pre;  //被删除节点的后节点的前节点要指向被删除节点的前节点
                }
                break;
            }
            temp = temp.next;  //继续移动
        }
    }

    //按照num大小顺序进行添加
    public void addNodeByOrder(PreNextNode node){
        PreNextNode temp = head;
        while(true){
            if(temp.next==null){  //此时即直接添加在队尾即可
                temp.next = node;
                node.pre = temp;
                break;
            }
            if(temp.next.num > node.num){
                PreNextNode tempNode = temp.next;  //先保存一下
                temp.next = node;  //更改temp的后节点指向我们的新节点
                node.next = tempNode;  //新节点的后节点再指向我们保存好的原先的后节点
                node.pre = temp;     //新节点的前节点指向temp
                tempNode.pre = node;  //我们保存好的原先的后节点的前节点指向新节点
                break;
            }
            if(temp.next.num == node.num){
                System.out.println("有相同的num,添加失败！");
                break;
            }
            temp = temp.next;
        }
    }

    //更新节点
    public void updateNode(PreNextNode node){
        PreNextNode temp = head.next;
        while(true){
            if(temp==null){
                System.out.println("没找到要更新的节点对应的num！");
                break;
            }
            if(temp.num == node.num){
                temp.pre.next = node;
                node.pre = temp.pre;
                if(temp.next!=null){
                    temp.next.pre = node;
                    node.next = temp.next;
                }

                break;
            }
            temp = temp.next;
        }
    }

    //直接添加节点
    public void addNode(PreNextNode node){
        PreNextNode temp = head;
        while(true){
            if(temp.next==null){
                break;
            }
            temp = temp.next;
        }

        temp.next = node;
        node.pre = temp;
    }

    public void nodeList(){
        PreNextNode temp = head;
        while(true){
            if(temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

}

class Test{
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addNodeByOrder(new PreNextNode(3,"a","aa"));
        doubleLinkedList.addNodeByOrder(new PreNextNode(2,"b","bb"));
        doubleLinkedList.addNodeByOrder(new PreNextNode(1,"c","cc"));

        doubleLinkedList.nodeList();
        System.out.println("==================");
        doubleLinkedList.updateNode(new PreNextNode(3,"cd","ccdd"));
        doubleLinkedList.nodeList();
        System.out.println("==================");
        doubleLinkedList.deleteNode(3);
        doubleLinkedList.nodeList();
    }
}

class PreNextNode{
    int num;
    String name;
    String nickname;
    PreNextNode next;
    PreNextNode pre;


    public PreNextNode(int num, String name, String nickname) {
        this.num = num;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

这篇关于数据结构与算法Java——链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！