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

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

目录概述链表单向链表单向链表实现Node类add方法remove方法get方法set方法contain方法main完整代码

概述

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

链表

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

链表包括三类:

单向链表双向链表循环链表

单向链表

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

单向链表实现

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 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->NULL1->0->NULL2->1->0->NULL3->2->1->0->NULL4->3->2->1->0->NULL5->4->3->2->1->0->NULL6->5->4->3->2->1->0->NULL7->6->5->4->3->2->1->0->NULLtruefalse9->7->5->4->3->2->1->0->NULL7->5->4->3->2->1->0->NULL5->4->3->2->1->0->NULL4->3->2->1->0->NULL3->2->1->0->NULL2->1->0->NULL1->0->NULL0->NULLNULL

完整代码

public class SingleLinkedList {

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() {

duhttp://mmyHead = 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 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);

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。