Java教程

算法入门 - 链表的实现及应用(Java版本)

本文主要是介绍算法入门 - 链表的实现及应用(Java版本),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

之前我们学习了动态数组,虽然比原始数组的功能强大了不少,但还不是完全纯动态的(基于静态数组实现的)。这回要讲的链表则是正儿八经的动态结构,是一种非常灵活的数据结构。

链表的基本结构

链表由一系列单一的节点组成,将它们一个接一个地链接起来,就形成了链表。链表虽然没有长度上的限制,但是节点之间需要储存关联关系。所以可以很自然地想到,你得知道前一个元素是啥,才能在它后面继续接新的元素。如果后面没元素可接,那么就在链表尾部接一个空值,代表链表结束。
我们从一个空链表开始,依次往链表中添加元素:

1.初始链表为空;
2.添加元素3后,3后面再无元素,所以要接一个空节点;
3.再依次添加元素4、6,结束后在末尾再接个空节点。
所以,如果用代码表示链表的结构,就可以这样描述:

public class LinkedList<E>{
    // 节点类
    private class Node {
        public E element;   // 节点储存的元素值
        public Node next;   // 指向的下一个链接节点

        public Node(E element, Node node) {
            this.element = element;
            this.next = node;
        }

        public Node(E element) {
            this.element = element;
            this.next = null;
        }

        public Node() {

        }
    }

    private Node head;  // 头节点
    private int size;   // 链表长度

    public LinkedList(){
        this.head = null;
        this.size = 0;
    }
}

我们用 head 表示头节点,即链表头部的节点。容易知道,每个链表只有一个头节点,且初始头节点为空。

带索引的链表

上面说了,如果要添加节点,需要知道前一个节点是啥。其实在一般情况下(只在链表尾部添加),前一个节点总是这个链表的最后一个节点。但是这里我们搞得稍微复杂一点,把链表也设计成可以根据索引,在链表的任何位置添加节点(虽然正常情况下链表无索引一说)。如果是这样的话,要在 index 处添加节点,就得从 head 开始遍历,知道 index-1 处(方便起见就叫 prev 节点)的节点是谁,然后再把 prev.next 指向新节点。这里有一个细节,就是如果 index 后面还有节点的话,就需要先把新节点的 next 指向 index节点(即prev.next),再把 prev 节点的next指向新节点。假如有一个长度为3的链表,现在要在index=1处添加新节点:

这里由于 head 节点正好就是 prev 节点,所以不用遍历。
如果是往头节点的位置添加元素的话,是没有prev节点的,所以需要特殊处理:

对于删除节点来说,也需要对头节点做特殊处理。但是这种特殊处理意味着更多的代码,而且每次都要进行条件判断。如果能在 head 头节点前面再增加一个节点,而这个节点本身又不参与存储元素,应该就能解决我们的问题。

dummyHead - 头节点的prev节点

dummyHead 就是我们为了方便添加头节点而新增的节点,dummy 的意思是它不是真正的节点,对外也无法访问。一个含有 dummyHead 的初始化链表如下:

转换成代码的话,就是这样:

public class LinkedList<E>{
    // 节点类
    private class Node{
    ... ...
    }

    private Node dummyHead;  // dummyHead节点
    private int size;   // 链表长度

    public LinkedList(){
        this.dummyHead= new Node();  // 生成dummyHead节点
        this.size = 0;
    }
}

可以看见,我们只声明了 dummyHead,而没有声明 head 头节点,因为 dummyHead 的下一个节点指向的就是 head 节点,如果想访问 head 节点,直接调用 dummyHead.next 就可以了。
有了 dummyHead,无论是添加还是删除节点,我们都可以遵循同一流程,而不必对谁特殊对待,影响整体性能。
节点添加流程:

节点删除流程:

节点访问流程:

我们之前一直着重在说节点增删的问题,其实访问节点比较简单,只要从头节点开始(dummyHead.next),遍历到索引位置,即可访问到目标节点。

代码实现

基于以上逻辑,我们就可以实现链表了。

package com.algorithm.linkedlist;

import java.lang.String;

// 添加head元素和索引元素分情况处理
public class LinkedList<E> {
    // 节点类
    private class Node {
        public E element;   // 节点储存的元素值
        public Node next;   // 指向的下一个链接节点

        public Node(E element, Node node) {
            this.element = element;
            this.next = node;
        }

        public Node(E element) {
            this.element = element;
            this.next = null;
        }

        public Node() {

        }
    }

    private Node dummyHead;  // 链表dummy节点
    private int size;   // 链表长度

    public LinkedList() {
        this.dummyHead = new Node();
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return getSize() == 0;
    }

    // 添加节点
    public void add(int index, E element) {
        if (index < 0 || index > getSize()) throw new IllegalArgumentException("index must > 0 and <= size!");
        // prev节点的初始值为dummyHead
        Node prev = dummyHead;
        // 通过遍历找到prev节点
        for (int i = 0; i < index; i++) prev = prev.next;
        // 将new Node的next节点指向prev.next,再把prev节点的next指向new Node
        prev.next = new Node(element, prev.next);
        size++;
    }

    public void addFirst(E element) {
        add(0, element);
    }

    public void addLast(E element) {
        add(getSize(), element);
    }

    // 移除节点
    public E remove(int index) {
        if (index < 0 || index >= getSize()) throw new IllegalArgumentException("index must > 0 and < size!");
        if (getSize() == 0) throw new IllegalArgumentException("Empty Queue, please enqueue first!");
        // prev节点的初始值为dummyHead
        Node prev = dummyHead;
        // 通过遍历找到prev节点
        for (int i = 0; i < index; i++) prev = prev.next;
        // 储存待删除节点
        Node delNode = prev.next;
        // 跳过delNode
        prev.next = delNode.next;
        // 待删除节点后接null
        delNode.next = null;
        size--;
        return delNode.element;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(getSize() - 1);
    }

    // 查找元素所在节点位置
    public int search(E element) {
        // 从头节点开始遍历
        Node current = dummyHead.next;
        for (int i = 0; i < getSize(); i++) {
            if (element.equals(current.element)) return i;
            current = current.next;
        }
        return -1;
    }

    // 判断节点元素值
    public boolean contains(E element) {
        return search(element) != -1;
    }

    // 获取指定位置元素值
    public E get(int index) {
        if (index < 0 || index >= getSize()) throw new IllegalArgumentException("index must > 0 and < size!");
        // 从头节点开始遍历
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) current = current.next;
        return current.element;
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(getSize() - 1);
    }

    // 设置节点元素值
    public void set(int index, E element) {
        // 从头节点开始遍历
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) current = current.next;
        current.element = element;
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append(String.format("LinkedList: size = %d\n", getSize()));
        Node current = dummyHead.next;
        for (int i = 0; i < getSize(); i++) {
            str.append(current.element).append("->");
            current = current.next;
        }
        str.append("null");
        return str.toString();
    }

    // main函数测试
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            linkedList.add(i, i);
            System.out.println(linkedList);
        }
        // 删除首尾节点
        linkedList.removeFirst();
        linkedList.removeLast();
        System.out.println(linkedList);
    }
}

/*
输出内容:
LinkedList: size = 1
0->null
LinkedList: size = 2
0->1->null
LinkedList: size = 3
0->1->2->null
LinkedList: size = 4
0->1->2->3->null
LinkedList: size = 5
0->1->2->3->4->null
LinkedList: size = 3
1->2->3->null
*/

使用链表实现栈

实现了链表后,我们仿照之前的动态数组,也实现一下栈和队列这两种较基础的数据结构。如果需要了解栈和队列,可以看之前的这篇文章。
在写代码前,我们先来分析一下如何实现。栈是一种后进先出的结构,而通过上面对链表的学习,可以发现链表的 head 头节点位置与栈的栈顶非常相似,节点可以通过头节点直接进入链表,也可以直接从头节点脱离链表,而且这两种操作的时间复杂度都是 O(1) 级别的(prev 节点无需移动)。找到了这个特点,就可以很快地利用链表实现栈。

我们还是使用之前的接口实现栈:

package com.algorithm.stack;

public interface Stack <E> {
    void push(E element);   // 入栈
    E pop();                // 出栈
    E peek();               // 查看栈顶元素
    int getSize();          // 获取栈长度
    boolean isEmpty();      // 判断栈是否为空

}

具体实现:

package com.algorithm.stack;


import com.algorithm.linkedlist.LinkedList;

public class LinkedListStack<E> implements Stack<E>{
    private LinkedList<E> linkedList; // 使用链表储存栈元素

    public LinkedListStack(){
        linkedList = new LinkedList<>();
    }

    // 把链表头作为栈顶,始终对链表头进行操作
    // 入栈
    @Override
    public void push(E element) {
        linkedList.addFirst(element);
    }

    // 出栈
    @Override
    public E pop() {
        return linkedList.removeFirst();
    }

    // 查看栈顶元素
    @Override
    public E peek() {
        return linkedList.getFirst();
    }

    // 查看栈中元素个数
    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    // 查看栈是否为空
    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public String toString() {
        return "Stack: top [" + linkedList + "] tail";
    }

    // main函数测试
    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        for (int i=0;i<5;i++){
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

/*
输出结果:
Stack: top [0->null] tail
Stack: top [1->0->null] tail
Stack: top [2->1->0->null] tail
Stack: top [3->2->1->0->null] tail
Stack: top [4->3->2->1->0->null] tail
Stack: top [3->2->1->0->null] tail
*/

数组栈VS链表栈

截至目前,我们已经通过两种方式实现了栈,接下来不妨对比一下两种实现方式的性能孰高孰低。可以通过出栈和入栈两种操作进行评估:

package com.algorithm.stack;

import java.util.Random;

public class PerformanceTest {
    public static double testStack(Stack<Integer> stack, int testNum){
        // 起始时间
        long startTime = System.nanoTime();
        // 使用随机数测试
        Random random = new Random();
        // 入栈测试
        for (int i=0;i<testNum;i++) stack.push(random.nextInt(Integer.MAX_VALUE));
        // 出栈测试
        for (int i=0;i<testNum;i++) stack.pop();
        // 结束时间
        long endTime = System.nanoTime();
        // 返回测试时长
        return (endTime - startTime) / 1000000000.0;

    }

    public static void main(String[] args) {
        // 数组栈
        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        double arrayTime = testStack(arrayStack, 1000000);
        System.out.println("ArrayStack: " + arrayTime);
        // 链表栈
        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        double linkedTIme = testStack(linkedListStack, 1000000);
        System.out.println("LinkedListStack: " + linkedTIme);
    }
}

/*
输出结果:
// testNum = 10万次的测试结果
ArrayStack: 0.0167257
LinkedListStack: 0.0120104

// testNum = 100万次的测试结果
ArrayStack: 0.0509282
LinkedListStack: 0.2121052
*/

第一次使用10万个随机数进行测试时,两者的性能差不多,链表似乎还有小小的优势;而当使用100万个数测试时,链表要明显慢于数组。原因是链表在添加节点的过程中,需要不断地new一个新的节点,而这个new的过程需要寻找新的地址,所以随着次数的增大,耗时变得越来越明显。而数组是先统一申请一批,满了再继续通过resize申请(个数根据数组长度)。但是如果先执行链表,后执行数组,又会出现不同的结果:

public class PerformanceTest {
    ... ...

    public static void main(String[] args) {
        // 链表栈
        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        double linkedTime = testStack(linkedListStack, 1000000);
        System.out.println("LinkedListStack: " + linkedTime);
        // 数组栈
        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        double arrayTime = testStack(arrayStack, 1000000);
        System.out.println("ArrayStack: " + arrayTime);

    }
}

/*
输出结果:
LinkedListStack: 0.0368811
ArrayStack: 0.054051
*/

这下链表又比数组快了

这篇关于算法入门 - 链表的实现及应用(Java版本)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!