Java链表(Linked List)基本原理与实现方法入门示例

下面是Java链表(Linked List)基本原理与实现方法入门示例的完整攻略。

什么是链表

链表是一种线性的数据结构,由一系列节点组成。每个节点都包含了数据和指向下一个节点的指针。

相比于数组,链表的一个主要优点是在插入、删除元素时不需要移动其他元素,因为每个节点都有指向下一个节点的指针。但是,链表的缺点是不能像数组一样随机访问,只能从头部开始遍历。

实现方法

Java实现单向链表

Java实现单向链表需要定义一个Node类,用于表示链表中的节点。定义一个链表类LinkedList,拥有添加节点方法(addNode)、删除节点方法(deleteNode)、遍历节点方法(traverseNodes)、清空链表方法等方法。

例如,以下为Java实现单向链表的示例代码:

public class Node {
    int data;
    Node next;

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

public class LinkedList {
    Node head;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void deleteNode(int data) {
        Node current = head;
        Node previous = null;
        while (current != null && current.data != data) {
            previous = current;
            current = current.next;
        }
        if (current != null) {
            if (previous == null) {
                head = current.next;
            } else {
                previous.next = current.next;
            }
        }
    }

    public void traverseNodes() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    public void clearList() {
        head = null;
    }
}

Java实现双向链表

Java实现双向链表需要在Node类中再添加前驱节点(previous)的指针,链表类中添加反向遍历节点方法(reverseTraverseNodes),其他方法和单向链表的实现类似。

例如,以下为Java实现双向链表的示例代码:

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

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

public class DoublyLinkedList {
    Node head;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.previous = current;
        }
    }

    public void deleteNode(int data) {
        Node current = head;
        while (current != null && current.data != data) {
            current = current.next;
        }
        if (current != null) {
            if (current.previous == null) {
                head = current.next;
                if (head != null) {
                    head.previous = null;
                }
            } else {
                current.previous.next = current.next;
                if (current.next != null) {
                    current.next.previous = current.previous;
                }
            }
        }
    }

    public void traverseNodes() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    public void reverseTraverseNodes() {
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        while (current != null) {
            System.out.println(current.data);
            current = current.previous;
        }
    }

    public void clearList() {
        head = null;
    }
}

示例说明

以下为使用单向链表实现LIFO(后进先出)栈的示例代码:

public class Stack {
    LinkedList list;

    public Stack() {
        list = new LinkedList();
    }

    public void push(int data) {
        list.addNode(data);
    }

    public int pop() {
        Node current = list.head;
        if (current == null) {
            throw new NoSuchElementException();
        } else if (current.next == null) {
            list.head = null;
            return current.data;
        } else {
            while (current.next.next != null) {
                current = current.next;
            }
            int data = current.next.data;
            current.next = null;
            return data;
        }
    }

    public void printStack() {
        list.traverseNodes();
    }
}

使用方式:

Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);  // 栈中元素为 3 -> 2 -> 1
stack.pop();    // 弹出元素3,栈中元素为 2 -> 1
stack.push(4);  // 栈中元素为 4 -> 2 -> 1
stack.printStack();  // 输出 4 2 1

以下为使用双向链表实现LIFO(后进先出)队列的示例代码:

public class Queue {
    DoublyLinkedList list;

    public Queue() {
        list = new DoublyLinkedList();
    }

    public void enqueue(int data) {
        list.addNode(data);
    }

    public int dequeue() {
        Node current = list.head;
        if (current == null) {
            throw new NoSuchElementException();
        } else if (current.next == null) {
            list.head = null;
            return current.data;
        } else {
            list.head = current.next;
            current.next.previous = null;
            return current.data;
        }
    }

    public void printQueue() {
        list.traverseNodes();
    }
}

使用方式:

Queue queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);  // 队列中元素为 1 <- 2 <- 3
queue.dequeue();   // 弹出元素1,队列中元素为 2 <- 3
queue.enqueue(4);  // 队列中元素为 2 <- 3 <- 4
queue.printQueue();  // 输出 2 3 4

以上两个示例代码对于链表的基本操作进行了展示,并且演示了如何通过链表实现栈和队列。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java链表(Linked List)基本原理与实现方法入门示例 - Python技术站

(0)
上一篇 2023年5月26日
下一篇 2023年5月26日

相关文章

  • response.setContentType()的作用及MIME参数详解

    下面是“response.setContentType()的作用及MIME参数详解”的完整攻略。 1. response.setContentType()的作用 在Java Web开发中,我们经常需要向客户端发送响应报文,使用response.setContentType()可以告诉浏览器我们发送的数据类型、编码方式等信息。 其中,response是Web应…

    Java 2023年6月15日
    00
  • FckEditor 中文配置手册详细说明

    FckEditor 中文配置手册详细说明 FckEditor 是一个免费的 HTML 编辑器,它具有跨浏览器兼容性和 WYSIWYG(所见即所得)编辑功能。本文将提供 FckEditor 中文配置手册的详细说明,包括安装、配置和使用 FckEditor 的示例。 安装 FckEditor 下载 FckEditor,可以在官方网站(https://ckedit…

    Java 2023年6月15日
    00
  • 详解Java的Struts框架中上传文件和客户端验证的实现

    详解Java的Struts框架中上传文件和客户端验证的实现 上传文件的实现 在 Struts 框架中,文件上传可以通过使用第三方库来实现,如:commons-fileupload 和 commons-io。 下面是文件上传的实现步骤: 导入文件上传相关的 jar 包: commons-fileupload-x.x.jar commons-io-x.x.jar…

    Java 2023年5月20日
    00
  • SpringBoot浅析安全管理之基于数据库认证

    SpringBoot浅析安全管理之基于数据库认证 在SpringBoot中,我们可以使用Spring Security来实现安全管理。本文将以基于数据库认证的方式为例,讲解SpringBoot安全管理的实现过程。 基础知识 在使用Spring Security进行安全管理之前,我们需要掌握以下一些基础知识: Spring Security的基本概念(如认证、…

    Java 2023年6月3日
    00
  • Java中数组的定义与使用

    Java中数组的定义与使用 在Java中,数组可以说是最常用的数据结构之一了。在Java中,数组具有以下的特点: 数组是一种引用数据类型; 数组中的元素类型必须一致,可以是Java中任何一种数据类型或者是自定义的数据类型; 数组的长度确定后不能再修改,要修改必须新建一个数组。 数组的定义 在Java中定义一个数组,需要指定数组的类型、名称和长度。具体语法如下…

    Java 2023年5月26日
    00
  • Spring Data JPA映射自定义实体类操作

    Spring Data JPA映射自定义实体类操作攻略 Spring Data JPA 是 Spring Data 的一种实现,旨在简化 JPA 的开发工作。在实际开发中,我们经常需要对实体类进行一些自定义操作,本篇攻略将介绍如何在 Spring Data JPA 中映射自定义实体类操作。 准备工作 在开始前,需要准备好以下工作: JDK 1.8 或以上 S…

    Java 2023年6月3日
    00
  • 详解Java编写并运行spark应用程序的方法

    详解Java编写并运行Spark应用程序的方法 本文将详细讲解如何使用Java编写并运行Spark应用程序,包括以下内容: 环境搭建 创建Spark应用程序 编写代码 打包和提交应用程序 示例说明 1. 环境搭建 首先,您需要在本地或者远程安装和配置Spark环境。安装和配置Spark环境包括以下几个步骤: 下载Spark安装包 解压安装包 配置环境变量 完…

    Java 2023年5月23日
    00
  • java对象数组实现学生信息管理系统

    Java对象数组实现学生信息管理系统攻略 在Java中,我们可以使用对象数组来实现一个学生信息管理系统。我们可以将学生信息作为一个对象,使用对象数组来存储多个学生的信息。下面是实现学生信息管理系统的完整攻略。 1. 定义学生信息类 我们首先需要定义一个学生信息类,用于存储学生的信息,包括姓名、年龄、性别、学号等。以下是一个示例: public class S…

    Java 2023年5月24日
    00
合作推广
合作推广
分享本页
返回顶部