双向链表的一些操作(Java)

如何根据值创建有序双向链表

package clwAhu;

import java.util.Scanner;

public class DoubleLinkListDemo {
    public static void main(String[] args) {

        DoubleLinkList linkList = new DoubleLinkList();

        linkList.add(2);
        linkList.add(1);
        linkList.add(3);

        Node head = linkList.getHead();
        showLinkList(head);
        setHeadNodeLength(head);
        System.out.println("链表的长度为" + head.val);

        Scanner scanner = new Scanner(System.in);
        System.out.print("输入带查找的值:");
        int val = scanner.nextInt();

        System.out.println("带查找的节点为" + searchNode(head, val));

    }

    /**
     * 根据链表的头节点和给定的值查找节点
     *
     * @param head 链表的头节点
     * @param val  待查找的值
     * @return 如果存在,返回节点,不存在返回null
     */
    public static Node searchNode(Node head, int val) {
        Node curr = head.next;
        while (curr != null) {
            if (curr.val == val) {
                return curr;
            }
            curr = curr.next;
        }
        return null;
    }

    /*遍历双向链表*/
    public static void showLinkList(Node head) {
        Node temp = head.next;

        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 得到链表的长度
     *
     * @param head 链表的头节点
     * @return 返回链表的长度
     */
    public static int getLinkListLength(Node head) {
        int len = 0;
        Node temp = head;

        while (temp.next != null) {
            len++;
            temp = temp.next;
        }
        return len;
    }

    /**
     * 头节点的值存放链表的长度
     *
     * @param head 链表的头节点
     */
    public static void setHeadNodeLength(Node head) {
        head.val = getLinkListLength(head);
    }
}


class DoubleLinkList {
    // 头节点中存放链表的长度
    public Node head = new Node(-1);

    /**
     * 构造有序双向链表
     *
     * @param val 节点值
     */
    public void add(int val) {
        Node node = new Node(val);

        if (head.next == null) {
            node.prev = head;
            head.next = node;
        } else {
            Node curr = head;

            while (curr.next != null && curr.next.val < val) {
                curr = curr.next;
            }

            if (curr.next != null) {
                node.next = curr.next;
                curr.next.prev = node;
            }
            node.prev = curr;
            curr.next = node;
        }

    }

    /**
     * 返回头节点
     *
     * @return 返回头节点
     */
    public Node getHead() {
        return head;
    }
}

class Node {
    int val;
    Node prev;
    Node next;

    public Node(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }
}
上一篇:Java算法之反转链表


下一篇:XSHELL下直接下载文件到本地(Windows)