乐趣区

关于java:链表

jiezi

链表由结点组成，每个结点除了保留本身的数据，还须要有指向其余结点的指针。与数组相比，链表在物理存储上是不间断的，不能通过下标进行随机拜访来获取元素。然而链表能够很容易的通过调整指针的指向实现减少和删除结点。

按指针的指向，链表分为：

  • 单向链表
  • 双向链表

单向链表

单向链表的结点只有一个指向下一个结点的指针。

先创立一个结点对象，蕴含一个指针属性 next：

public class Node {
    private int data;
    private Node next;

    public Node() {}

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

    public Node(Node next) {this.next = next;}

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public int getData() {return data;}

    public void setData(int data) {this.data = data;}

    public Node getNext() {return next;}

    public void setNext(Node next) {this.next = next;}

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

将对单向链表的罕用操作封装到类中：

public class SingleLinkedList {

    /**
     * 遍历单向链表
     * @param head 头结点
     */
    public void list(Node head) {if (head == null || head.getNext() == null) {System.out.println("the List is empty");
            return;
        }

        Node temp = head.getNext();
        while (true) {if (temp == null) {break;}
            System.out.println(temp);
            temp = temp.getNext();}
    }

    /**
     * 获取单向链表长度（结点个数），不统计头结点
     * @param head 头结点
     * @return 返回链表长度（结点个数）*/
    public int getLength(Node head) {if (head == null || head.getNext() == null) {return 0;}

        Node temp = head.getNext();
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.getNext();}
        return length;
    }

    /**
     * 增加结点到单向链表的最初
     * 1. 找到以后单向链表的最初结点
     * 2. 将最初结点的 next 指向新结点
     * @param head 头结点
     * @param node
     */
    public boolean add(Node head, Node node) {if (head == null || node == null) {return false;}

        Node temp = head;
        while (true) {if (temp.getNext() == null) {break;}
            temp = temp.getNext();}
        temp.setNext(node);
        return true;
    }

    /**
     * 增加结点到指定结点前面
     * @param node 指定的结点
     * @param insertNode 增加的结点
     */
    public boolean insert(Node node, Node insertNode) {if (node == null || insertNode == null) {return false;}

        if (node.getNext() == null) {node.setNext(insertNode);
            return true;
        }

        insertNode.setNext(node.getNext());
        node.setNext(insertNode);
        return true;
    }

    /**
     * 删除指定结点，须要找到指定结点的前一个结点
     * @param deleteNode 删除的结点
     */
    public boolean delete(Node head, Node deleteNode) {if (head == null || deleteNode == null || head == deleteNode) {return false;}

        Node temp = head;
        while (true) {if (temp.getNext() == null) {return false;}
            if (temp.getNext() == deleteNode) {break;}
            temp = temp.getNext();}
        temp.setNext(temp.getNext().getNext());
        return true;
    }
}

进行测试：

public static void main(String[] args) {Node head = new Node(0);
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        System.out.println("=== 增加结点到最初 ===");
        singleLinkedList.add(head,node1);
        singleLinkedList.add(head,node2);
        singleLinkedList.add(head,node3);
        singleLinkedList.add(head,node4);
        System.out.println("链表结点为：");
        singleLinkedList.list(head);
        System.out.println("链表长度为：");
        System.out.println(singleLinkedList.getLength(head));
        System.out.println("=== 增加结点到指定结点前面 ===");
        Node node5 = new Node(5);
        singleLinkedList.insert(node2,node5);
        System.out.println("链表结点为：");
        singleLinkedList.list(head);
        System.out.println("链表长度为：");
        System.out.println(singleLinkedList.getLength(head));
        System.out.println("=== 删除指定结点 ===");
        singleLinkedList.delete(head,node5);
        System.out.println("链表结点为：");
        singleLinkedList.list(head);
        System.out.println("链表长度为：");
        System.out.println(singleLinkedList.getLength(head));
    }

输入后果为：

=== 增加结点到最初 ===
链表结点为：Node{data=1}
Node{data=2}
Node{data=3}
Node{data=4}
链表长度为：4
=== 增加结点到指定结点前面 ===
链表结点为：Node{data=1}
Node{data=2}
Node{data=5}
Node{data=3}
Node{data=4}
链表长度为：5
=== 删除指定结点 ===
链表结点为：Node{data=1}
Node{data=2}
Node{data=3}
Node{data=4}
链表长度为：4

反转单向链表

指定一个新的头结点，将每一个解决的结点都放在新的头结点之后。

    /**
     * 反转单向链表
     * @param head
     * @return
     */
    public Node reverse(Node head) {if (head == null || head.getNext() == null) {return head;}
        // 指定一个新的头结点
        Node newHead = new Node(0);
        // 指定以后解决的结点
        Node curr = head.getNext();
        // 指定以后解决结点的下一结点
        Node next = null;
        while (curr != null) {
            // 第一步：获取反转前以后结点的下一结点
            next = curr.getNext();
            // 第二步：指定以后结点的下一结点为新的头结点的下一结点
            curr.setNext(newHead.getNext());
            // 第三步：指定新的头结点的下一结点为以后解决的结点
            newHead.setNext(curr);
            // 持续解决后一个结点
            curr = next;
        }
        // 指定原头结点的下一结点为新头结点的下一结点
        head.setNext(newHead.getNext());
        return head;
    }

第一个结点解决示意图：

第二个结点解决示意图：

后面的循环遍历都没有思考单向列表成环的状况，如果有环的话，就会导致有限循环，能够通过快慢指针来查看环：

/**
     * 检测环
     * @param head 头结点
     * @return
     */
    public boolean checkCircle(Node head) {if (head == null) {return false;}
        Node fast = head.getNext();
        Node slow = head;

        while (fast != null && fast.getNext() != null) {fast = fast.getNext().getNext();
            slow = slow.getNext();

            if (slow == fast) {return true;}
        }

        return false;
    }

双向链表

双向链表的结点有两个指针，别离指向上一个结点和下一个结点。

先创立一个结点对象，蕴含两指针属性 pre 和 next：

public class DoubleNode {

    private int data;
    private DoubleNode pre;
    private DoubleNode next;

    public DoubleNode() {}

    public DoubleNode(int data) {this.data = data;}

    public DoubleNode(DoubleNode pre, DoubleNode next) {
        this.pre = pre;
        this.next = next;
    }

    public DoubleNode(int data, DoubleNode pre, DoubleNode next) {
        this.data = data;
        this.pre = pre;
        this.next = next;
    }

    public int getData() {return data;}

    public void setData(int data) {this.data = data;}

    public DoubleNode getPre() {return pre;}

    public void setPre(DoubleNode pre) {this.pre = pre;}

    public DoubleNode getNext() {return next;}

    public void setNext(DoubleNode next) {this.next = next;}

    @Override
    public String toString() {
        return "DoubleNode{" +
                "data=" + data +
                '}';
    }
}

将对双向链表的罕用操作封装到类中：

public class DoubleLinkedList {

    /**
     * 遍历双向链表
     * @param head 头结点
     */
    public void list(DoubleNode head) {if (head.getNext() == null) {System.out.println("the List is empty");
            return;
        }

        DoubleNode temp = head.getNext();
        while (true) {if (temp == null) {break;}
            System.out.println(temp);
            temp = temp.getNext();}
    }

    /**
     * 获取双向链表长度（结点个数），不统计头结点
     * @param head 头结点
     * @return 返回链表长度（结点个数）*/
    public int getLength(DoubleNode head) {if (head == null || head.getNext() == null) {return 0;}

        DoubleNode temp = head.getNext();
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.getNext();}
        return length;
    }

    /**
     * 增加结点到双向链表的最初
     * 1. 找到以后双向链表的最初结点
     * 2. 将最初结点的 next 指向新结点
     * 3. 将新结点的 pre 指向前一结点
     * @param head 头结点
     * @param node 减少的结点
     */
    public void add(DoubleNode head, DoubleNode node) {
        DoubleNode temp = head;
        while (true) {if (temp.getNext() == null) {break;}
            temp = temp.getNext();}
        temp.setNext(node);
        node.setPre(temp);
    }

    /**
     * 增加结点到指定结点前面
     * @param node 指定的结点
     * @param insertNode 增加的结点
     */
    public boolean insertAfter(DoubleNode node, DoubleNode insertNode) {if (node == null || insertNode == null) {return false;}

        if (node.getNext() == null) {node.setNext(insertNode);
            insertNode.setPre(node);
            return true;
        }

        insertNode.setPre(node);
        insertNode.setNext(node.getNext());
        node.getNext().setPre(insertNode);
        node.setNext(insertNode);
        return true;
    }

    /**
     * 增加结点到指定结点后面
     * @param node 指定的结点
     * @param insertNode 增加的结点
     */
    public boolean insertBefore(DoubleNode node, DoubleNode insertNode) {if (node == null || insertNode == null) {return false;}

        if (node.getPre() == null) {insertNode.setNext(node);
            node.setPre(insertNode);
            return true;
        }

        insertNode.setPre(node.getPre());
        insertNode.setNext(node);
        node.getPre().setNext(insertNode);
        node.setPre(insertNode);
        return true;
    }

    /**
     * 删除指定结点
     * @param deleteNode 删除的结点
     */
    public boolean delete(DoubleNode deleteNode) {if (deleteNode == null) {return false;}

        if (deleteNode.getPre() != null){deleteNode.getPre().setNext(deleteNode.getNext());
        }
        if (deleteNode.getNext() != null) {deleteNode.getNext().setPre(deleteNode.getPre());
        }
        return true;
    }

    /**
     * 检测环
     * @param head 头结点
     * @return
     */
    public boolean checkCircle(DoubleNode head) {if (head == null) {return false;}
        DoubleNode fast = head.getNext();
        DoubleNode slow = head;

        while (fast != null && fast.getNext() != null) {fast = fast.getNext().getNext();
            slow = slow.getNext();

            if (slow == fast) {return true;}
        }

        return false;
    }
}

进行测试：

public static void main(String[] args) {DoubleNode head = new DoubleNode(0);
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        DoubleNode node1 = new DoubleNode(1);
        DoubleNode node2 = new DoubleNode(2);
        DoubleNode node3 = new DoubleNode(3);
        DoubleNode node4 = new DoubleNode(4);
        System.out.println("=== 增加结点到最初 ===");
        doubleLinkedList.add(head,node1);
        doubleLinkedList.add(head,node2);
        doubleLinkedList.add(head,node3);
        doubleLinkedList.add(head,node4);
        System.out.println("链表结点为：");
        doubleLinkedList.list(head);
        System.out.println("链表长度为：");
        System.out.println(doubleLinkedList.getLength(head));
        System.out.println("=== 增加结点到指定结点前面 ===");
        DoubleNode node5 = new DoubleNode(5);
        doubleLinkedList.insertAfter(node2,node5);
        System.out.println("链表结点为：");
        doubleLinkedList.list(head);
        System.out.println("链表长度为：");
        System.out.println("=== 增加结点到指定结点后面 ===");
        DoubleNode node6 = new DoubleNode(6);
        doubleLinkedList.insertBefore(node2,node6);
        System.out.println("链表结点为：");
        doubleLinkedList.list(head);
        System.out.println("链表长度为：");
        System.out.println(doubleLinkedList.getLength(head));
        System.out.println("=== 删除指定结点 ===");
        doubleLinkedList.delete(node5);
        System.out.println("链表结点为：");
        doubleLinkedList.list(head);
        System.out.println("链表长度为：");
        System.out.println(doubleLinkedList.getLength(head));
    }

输入后果为：

=== 增加结点到最初 ===
链表结点为：DoubleNode{data=1}
DoubleNode{data=2}
DoubleNode{data=3}
DoubleNode{data=4}
链表长度为：4
=== 增加结点到指定结点前面 ===
链表结点为：DoubleNode{data=1}
DoubleNode{data=2}
DoubleNode{data=5}
DoubleNode{data=3}
DoubleNode{data=4}
链表长度为：=== 增加结点到指定结点后面 ===
链表结点为：DoubleNode{data=1}
DoubleNode{data=6}
DoubleNode{data=2}
DoubleNode{data=5}
DoubleNode{data=3}
DoubleNode{data=4}
链表长度为：6
=== 删除指定结点 ===
链表结点为：DoubleNode{data=1}
DoubleNode{data=6}
DoubleNode{data=2}
DoubleNode{data=3}
DoubleNode{data=4}
链表长度为：5

欢送关注我的公众号，一起学习。

退出移动版