java编程
搜索
分类

Java 数据结构与算法系列精讲之单向链表

作者：我是小白呀 时间：2023-07-10 08:22:12　

概述

从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.

Java 数据结构与算法系列精讲之单向链表

链表

链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大.

Java 数据结构与算法系列精讲之单向链表

链表包括三类:

  • 单向链表

  • 双向链表

  • 循环链表

单向链表

单向链表 (Single Linked List) 是链表中最简单的一种形式. 单向链表每个节点包含两个部分, 第一部分是信息, 第二部分是下一个节点. (元素 + 指针)

Java 数据结构与算法系列精讲之单向链表

单向链表实现

Node 类


// Node类
private class Node {

public E e;  // 元素
   private SingleLinkedList.Node next;  // 下一个节点

// 构造
   public Node(E e) {
       this.e = e;
       this.next = null;
   }

@Override
   public String toString() {
       return e.toString();
   }
}

add 方法


// 添加数据
public void add(int index, E e) {

// 检查索引是否越界
   if (index < 0 || index > size) {
       throw new RuntimeException("Invalid Index");
   }

// 获取index前一个节点
   SingleLinkedList.Node prev = dummyHead;
   for (int i = 0; i < index; i++) {
       prev = prev.next;
   }

// 添加数据
   SingleLinkedList.Node node = new SingleLinkedList.Node(e);
   node.next = prev.next;
   prev.next = node;
   size++;
}

remove 方法


// 删除数据
public void remove(int index) {

// 检查索引是否越界
   if (index < 0 || index > size) {
       throw new RuntimeException("Invalid Index");
   }

// 获取index前一个节点
   Node prev = dummyHead;
   for (int i = 0; i < index; i++) {
       prev = prev.next;
   }

// 删除数据
   Node retNode = prev.next;
   prev.next = retNode.next;

size --;
}

get 方法


// 通过索引获取链表数数据
public E get(int index) {

// 检查索引是否越界
   if (index < 0 || index > size) {
       throw new RuntimeException("Invalid Index");
   }

// 获取index前一个节点
   Node cur = dummyHead.next;
   for (int i = 0; i < index; i++) {
       cur = cur.next;
   }

return cur.e;
}

set 方法


// 通过索引设置链表数据
public E set(int index,E e) {

// 检查索引是否越界
   if (index < 0 || index > size) {
       throw new RuntimeException("Invalid Index");
   }

// 获取index前一个节点
   Node cur = dummyHead.next;
   for (int i = 0; i < index; i++) {
       cur = cur.next;
   }

// 设置新值
   cur.e = e;

return cur.e;
}

contain 方法


// 链表是否包含元素
public boolean contains(E e) {
       Node cur = dummyHead.next;

// 遍历所有节点
       while (cur != null) {
           if (cur.e.equals(e)) {
               return true;
           }
           cur = cur.next;
       }
   return false;
}

main


// main
public static void main(String[] args) {

// 创建单向链表
   SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

// 添加数据
   for (int i = 0; i < 8; i++) {
       singleLinkedList.addFirst(i);
       System.out.println(singleLinkedList);
   }

// 是否包含元素
   System.out.println(singleLinkedList.contains(0));
   System.out.println(singleLinkedList.contains(10));

// set
   singleLinkedList.set(0, 9);
   singleLinkedList.set(1, 7);
   System.out.println(singleLinkedList);

// 删除数据
   for (int i = 0; i < 8; i++) {
       singleLinkedList.remove(0);
       System.out.println(singleLinkedList);
   }
}

输出结果:

0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
6->5->4->3->2->1->0->NULL
7->6->5->4->3->2->1->0->NULL
true
false
9->7->5->4->3->2->1->0->NULL
7->5->4->3->2->1->0->NULL
5->4->3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL

完整代码


public class SingleLinkedList<E> {

private Node dummyHead;  // 头指针
   private int size;  // 链表大小

// Node类
   private class Node {

public E e;  // 元素
       private Node next;  // 下一个节点

// 构造
       public Node(E e) {
           this.e = e;
           this.next = null;
       }

@Override
       public String toString() {
           return e.toString();
       }
   }

// 构造
   public SingleLinkedList() {
       dummyHead = new Node(null);
       size = 0;
   }

// 表首添加元素
   public void addFirst(E e) {
       add(0, e);
   }

// 表尾添加元素
   public void addLast(E e){
       add(size, e);
   }

// 添加数据
   public void add(int index, E e) {

// 检查索引是否越界
       if (index < 0 || index > size) {
           throw new RuntimeException("Invalid Index");
       }

// 获取index前一个节点
       Node prev = dummyHead;
       for (int i = 0; i < index; i++) {
           prev = prev.next;
       }

// 添加数据
       Node node = new Node(e);
       node.next = prev.next;
       prev.next = node;
       size ++;
   }

// 删除数据
   public void remove(int index) {

// 检查索引是否越界
       if (index < 0 || index > size) {
           throw new RuntimeException("Invalid Index");
       }

// 获取index前一个节点
       Node prev = dummyHead;
       for (int i = 0; i < index; i++) {
           prev = prev.next;
       }

// 删除数据
       Node retNode = prev.next;
       prev.next = retNode.next;

size --;
   }

// 通过索引获取链表数数据
   public E get(int index) {

// 检查索引是否越界
       if (index < 0 || index > size) {
           throw new RuntimeException("Invalid Index");
       }

// 获取index前一个节点
       Node cur = dummyHead.next;
       for (int i = 0; i < index; i++) {
           cur = cur.next;
       }

return cur.e;
   }

// 通过索引设置链表数据
   public E set(int index,E e) {

// 检查索引是否越界
       if (index < 0 || index > size) {
           throw new RuntimeException("Invalid Index");
       }

// 获取index前一个节点
       Node cur = dummyHead.next;
       for (int i = 0; i < index; i++) {
           cur = cur.next;
       }

// 设置新值
       cur.e = e;

return cur.e;
   }

// 链表是否包含元素
   public boolean contains(E e) {
       Node cur = dummyHead.next;

// 遍历所有节点
       while (cur != null) {
           if (cur.e.equals(e)) {
               return true;
           }
           cur = cur.next;
       }
       return false;
   }

// 获取链表大小
   public int getSize() {
       return size;
   }

// 判断链表是否为空
   public boolean isEmpty() {
       return size == 0;
   }

@Override
   public String toString() {

StringBuilder builder = new StringBuilder();
       Node cur = dummyHead.next;
       while (cur != null) {
           builder.append(cur + "->");
           cur = cur.next;
       }
       builder.append("NULL");
       return builder.toString();
   }

// main
   public static void main(String[] args) {

// 创建单向链表
       SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();

// 添加数据
       for (int i = 0; i < 8; i++) {
           singleLinkedList.addFirst(i);
           System.out.println(singleLinkedList);
       }

// 是否包含元素
       System.out.println(singleLinkedList.contains(0));
       System.out.println(singleLinkedList.contains(10));

// set
       singleLinkedList.set(0, 9);
       singleLinkedList.set(1, 7);
       System.out.println(singleLinkedList);

// 删除数据
       for (int i = 0; i < 8; i++) {
           singleLinkedList.remove(0);
           System.out.println(singleLinkedList);
       }
   }
}

来源：https://iamarookie.blog.csdn.net/article/details/121885670

标签：Java,单向链表,数据结构,算法
0
投稿

猜你喜欢

  • 基于Kubernetes实现前后端应用的金丝雀发布(两种方案)

    2023-01-07 02:32:27

  • 关于jdk环境变量的配置方式解读

    2023-04-22 14:53:05

  • Android BottomSheet实现可拉伸控件

    2023-07-05 15:07:51

  • SpringBoot @PropertySource与@ImportResource有什么区别

    2023-08-22 02:02:47

  • Android形状图形与状态列表图形及九宫格图片超详细讲解

    2023-04-13 06:04:01

  • Java实现的双向匹配分词算法示例

    2023-06-23 08:29:32

  • springboot项目访问静态资源的配置代码实例

    2021-11-16 02:07:49

  • springBoot Junit测试用例出现@Autowired不生效的解决

    2023-01-24 12:57:59

  • 详解WPF中用户控件和自定义控件的使用

    2023-07-25 12:20:26

  • Android自定义view实现有header和footer作为layout使用的滚动控件

    2023-07-31 19:29:54

  • Java List的remove()方法踩坑

    2021-05-27 05:17:58

  • Android中Textview和图片同行显示(文字超出用省略号，图片自动靠右边)

    2023-02-25 04:52:37

  • 使用BindingResult 自定义错误信息

    2023-09-02 17:43:01

  • Struts2学习笔记(9)-Result配置全局结果集

    2022-04-09 11:33:10

  • Java SE求解汉诺塔问题的示例代码

    2022-05-10 23:44:30

  • java遍历读取xml文件内容

    2023-11-12 09:59:09

  • java使用Hashtable过滤数组中重复值的方法

    2023-10-22 06:24:08

  • springboot集成shiro权限管理简单实现

    2023-10-27 13:39:02

  • 详解ASP.NET中Identity的身份验证代码

    2022-05-20 04:43:48

  • SpringBoot Admin 如何实现Actuator端点可视化监控

    2022-12-09 01:40:51
    • asp之家 软件编程 m.aspxhome.com