数据结构与算法--使用Java实现单链的LinkedList
·
上一篇博客中,使用Java实现了ArrayList的基本功能,博客链接如下:
今天继续实现另一种数据结构:LinkedList
循序渐进,先用单链表实现~
本篇博客所涉及到的代码,均已上传到github:
项目github链接
本篇博客涉及代码github链接
本篇博客要点如下:
一. 链表简介
LinkedList是和ArrayList一样重要的一种数据结构
我们常说:
LinkedList的底层数据结构是链表,查询慢,增删快,线程不安全,效率高
如果我们想要知道,它为什么具有这样的特性,就需要对链表这种数据结构有一个进一步的了解
链表概念
链表是一种物理存储单元上非连续、非顺序的存储结构，
数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表存储结构
因为本篇博文是以单链表实现LinkedList,因此这里以单链表进行举例:
从图片中,我们可以看到:
和数组的元素值存储数据不同,
对于链表中的每一个元素, 包含了存储元素的数据域,和存储下一个元素地址的指针域.
最后一个元素的指针域为空
同时,链表中逻辑上连续的元素,在物理存储结构又是不连续的,这一点也和数组不同
那么这种存储结构具有什么优点和缺点呢?
优点:
1.增删性能高
在新增数据时,只要将前驱节点的指针域指向新增的元素,将新增元素的指针域指向后继节点即可
在删除数据时,只要将删除元素前驱节点的指针域指向删除元素后继节点的指针域即可
(但这种性能高并不适用于所有的链表哦,请大家结合下面我写的单链的增删代码来判断一下单链是否具有这个优点)
所以,链表进行增删操作的时间复杂度T(n)=O(1).
而数组是O(n)
2.不存在闲置的情况
每一个节点,都包含了一个数据域和指向下一个元素地址的指针域,没有闲置.
从这个角度来说,节约内存资源
缺点:
1.操作难度大,理解成本高
姑且把这个算作为链表的一个缺点
对于我这种不够聪明的人来说,学习链表的成本确实高于数组!
2.查询效率低
链表的查询,只能从头结点开始遍历,根据指针域一个一个获取元素,
查询操作的时间复杂度为T(n)=O(n)
3.除了数值域,还要为指针域分配额外的空间
二.使用Java代码实现LinkedList
基于上述的了解: 我们可以开始试着手写一个简单的LinkedList
使用Java的人应该都知道,LinkedList和ArrayList一样,都实现了List接口
因此,ArrayList集合的操作,同样适用于LinkedList,只是实现方式有所差异.
集合大小,非空判断,增加元素,删除元素,修改元素,获取元素,字符串转换
我们把上面列举出来的每一种操作封装为一个方法,可以得到一个接口,如下:
List接口
public interface List {
// 返回线性表的大小,即数据元素的个数
int size();
// 返回线性表序号为i的数据元素
Object get(int i);
// 判断线性表是否包含数据元素e
boolean contains(Object e);
// 线性表为空返回true,否则返回false
boolean isEmpty();
// 返回数据元素e在线性表中的序号
int indexOf(Object e);
// 将数据元素e插入到线性表中的i号位置
void add(int i, Object e);
// 将元素e插入到线性表末尾
void add(Object e);
// 将元素e插入到元素obj之前
boolean addBefore(Object obj, Object e);
// 将元素e插到元素obj之后
boolean addAfter(Object obj, Object e);
// 删除线性表中序号为i的元素,并返回
Object remove(int i);
// 删除线性表中第一个与a相同的元素
boolean remove(Object e);
// 替换线性表中序号为i的数据元素为e,返回原数据元素
Object replace(int i, Object e);
}
Node类的引入
链表中的每个元素, 包含一个数据域和一个指针域
为了更形象的描述链表结构,我们把它抽象成一个实体类Node
用Object类型的数据data来表示数据域
用Node类型的数据next来表示链表的指针域
如下面的代码所示:
/**
* @author xmr
* @description 单链表 只能通过前驱节点找到后继节点,不能通过后继节点找到前驱节点
*/
public class Node {
Object data; // 要存储的数据
Node next; // 指向下一个节点的指针
public Node(Object data) {
super();
this.data = data;
}
public Node(Object data, Node next) {
super();
this.data = data;
this.next = next;
}
public Node() {
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
实现单链的LinkedList
我们需要两个成员变量来表示
LinkedList的头结点和大小
private Node head = new Node(); // 头结点,不存储数据,为了编码方便,以方便对空链表和只有一个节点的链表进行处理
private int size; // 单链表的节点个数
获取集合大小
成员变量size表示集合大小,返回它即可
@Override
public int size() {
return size;
}
获取集合元素
获取集合指定索引元素的数据域
@Override
public Object get(int i) {
// 首先要进行参数检查
if (i < 0 || i >= size) {
throw new RuntimeException("指针越界! " + i);
}
// 因为链表只能通过前驱节点的指针去寻找后继节点,所以链表的查询需要从头开始遍历
Node p = head;
for (int j = 0; j <= i; j++) {
p = p.next;
}
return p.data;
}
从代码中我们可以看到,链表查询的性能并不高,时间复杂度:T(n)=O(n)
获取指定元素第一次出现的索引
@Override
public int indexOf(Object e) {
Node p = head.next; // 这里p指的是链表的真正意义上的第一个元素,因为头结点的数据域永远为Null
for (int i = 0; i < size; i++) {
// 首先针对空值进行判断,以免出现空指针异常
if (e == null) {
if (p.data == null) {
return i;
}
} else {
if (e.equals(p.data)) {
return i;
}
}
p = p.next;
}
// 在链表中找不到对应的元素,返回-1
return -1;
}
判断集合是否包含指定元素
@Override
public boolean contains(Object e) {
// 这里我最初是采用遍历的方法进行判别的,后面想到,我在之前实现的indexOf方法
// 试想,若集合包含某个元素,则该元素在集合里对应的索引应该大于等于0
// 所以,我们在这里复用上面的indexOf方法,实现如下:
return indexOf(e) >= 0;
}
判断集合是否为空
@Override
public boolean isEmpty() {
// 集合为空,代表集合大小为0
return size == 0;
}
集合数据添加
添加元素有以下情况:一种是添加到集合指定索引位置,一种是添加到集合的最后
一种是添加到指定元素的前面,一种是添加到指定元素的后面
/*
添加元素到指定位置
思路:1. 找到要插入元素的前驱节点
2. 将前驱节点的指针指向该元素
3. 将该元素的指针指向后继节点
*/
@Override
public void add(int i, Object e) {
if (i > size || i < 0) {
throw new RuntimeException("指针越界! " + i);
}
// 找到前一个节点,从head节点开始
Node p = head;
for (int j = 0; j < i; j++) {
p = p.next;
}
// 新创建一个节点
Node newNode = new Node(e);
newNode.data = e; //新节点的数据域为要插入元素e
newNode.next = p.next;
// 指明新节点的直接后继节点
// 指明新节点的直接前驱节点
p.next = newNode;
size ++; // 添加完元素,链表的大小也要做出相应改变
}
/*
这里我们考虑到,插入到链表末尾,只是插入到指定位置的一种特殊情况
因此,直接调用上面的方法即可
*/
@Override
public void add(Object e) {
this.add(size, e);
}
/*
添加到指定元素的前面,若链表里没有该元素,返回false
*/
@Override
public boolean addBefore(Object obj, Object e) {
// 首先寻找到该元素,找不到就返回false
int index = indexOf(e);
if (index < 0) {
return false;
}
// 找到该元素的前一个节点
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
Node node = new Node(obj);
// 修改e前一个节点的指针,使其指向obj
node.data = obj;
node.next = p.next;
// 让obj的指针指向e的后继节点
p.next = node;
size++;
return true;
}
/*
添加到指定元素的后面,若链表里没有该元素,返回false
*/
@Override
public boolean addAfter(Object obj, Object e) {
// 首先寻找到该元素,找不到就返回false
int index = indexOf(e);
if (index < 0) {
return false;
}
// 找到该元素的后一个节点
Node p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
Node node = new Node(obj);
// 修改e前一个节点的指针,使其指向obj
node.data = obj;
node.next = p.next;
// 让obj的指针指向e的后继节点
p.next = node;
size++;
return true;
}
集合数据删除
/*
删除集合对应索引的元素,返回旧值
删除操作的关键点 : 将要删除元素的前驱节点的指针直接指向要删除元素的后继节点
*/
@Override
public Object remove(int i) {
if (i >= size || i < 0) {
throw new RuntimeException("指针越界! " + i);
}
Node p = head;
// 找到索引i的前一个元素
for (int j = 0 ; j < i; j++) {
p = p.next;
}
Node node = p.next; // 索引i所在位置的元素
// 将前一个元素的指针指向 索引i的后一个元素
p.next = p.next.next;
System.out.println(node);
size --;
return node;
}
/*
删除集合里指定的元素
思路: 我们可以找到该元素在链表中对应的索引
然后把它转换成通过索引进行删除的方式
*/
@Override
public boolean remove(Object e) {
int i = indexOf(e);
if (i < 0 || i >= size) {
return false;
}
remove(i);
return true;
}
集合数据替换
/*
将集合指定索引的元素替换为特定的值,并返回原数据元素
思路:集合元素的替换不需要考虑指针,
找到对应索引对应的元素,直接替换data域即可
*/
@Override
public Object replace(int i, Object e) {
if (i < 0 || i >= size) {
throw new RuntimeException("指针越界! " + i);
}
Node p = head;
for (int j = 0; j < i; j++) {
p = p.next;
}
// 将前一个元素的值替换为e
Node oldValue = p.next;
p.next.data = e;
return oldValue;
}
重写toString()方法
/*
对我来说,重写该方法的目的就是使输出变得更友好,
方便进行代码调试.如下:输出为[data1,data2]这种格式
*/
@Override
public String toString() {
if (size == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
Node p = head.next;
for (int i = 0; i < size; i++) {
if (i != size - 1) {
sb.append(p.data).append(",");
} else {
sb.append(p.data);
}
p = p.next;
}
sb.append("]");
return sb.toString();
}
如上,我们通过自己的方式实现了LinkedList的基本功能!
三. 全量代码分享
/**
* @author xmr
* @description 使用java语言实现单链表的基本功能
*/
public class SingleLinkedList implements List{
private Node head = new Node(); // 头结点,不存储数据,为了编码方便,以方便对空链表和只有一个节点的链表进行处理
private int size; // 单链表的节点个数
public static void main(String[] args) {
List list = new SingleLinkedList();
list.add(0, "32");
list.add(1, null);
list.addBefore("64", "32");
// list.remove(2);
list.replace(1, "18");
System.out.println(list.get(0));
System.out.println(list.size());
System.out.println(list.toString());
System.out.println(list.indexOf(null));
}
@Override
public int size() {
return size;
}
@Override
public Object get(int i) {
if (i < 0 || i >= size) {
throw new RuntimeException("指针越界! " + i);
}
Node p = head;
for (int j = 0; j <= i; j++) {
p = p.next;
}
return p.data;
}
@Override
public boolean contains(Object e) {
return indexOf(e) >= 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int indexOf(Object e) {
Node p = head.next;
for (int i = 0; i < size; i++) {
if (e == null) {
if (p.data == null) {
return i;
}
} else {
if (e.equals(p.data)) {
return i;
}
}
p = p.next;
}
return -1;
}
@Override
public void add(int i, Object e) {
if (i > size) {
throw new RuntimeException("指针越界! " + i);
}
// 找到前一个节点,从head节点开始
Node p = head;
for (int j = 0; j < i; j++) {
p = p.next;
}
// 新创建一个节点
Node newNode = new Node(e);
newNode.data = e;
newNode.next = p.next;
// 指明新节点的直接后继节点
// 指明新节点的直接前驱节点
p.next = newNode;
size ++;
}
@Override
public void add(Object e) {
this.add(size, e);
}
@Override
public boolean addBefore(Object obj, Object e) {
// 首先寻找到该元素,找不到就返回false
int index = indexOf(e);
if (index < 0) {
return false;
}
// 找到该元素的前一个节点
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
Node node = new Node(obj);
// 修改e前一个节点的指针,使其指向obj
node.data = obj;
node.next = p.next;
// 让obj的指针指向e的后继节点
p.next = node;
size++;
return true;
}
@Override
public boolean addAfter(Object obj, Object e) {
// 首先寻找到该元素,找不到就返回false
int index = indexOf(e);
if (index < 0) {
return false;
}
// 找到该元素的后一个节点
Node p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
Node node = new Node(obj);
// 修改e前一个节点的指针,使其指向obj
node.data = obj;
node.next = p.next;
// 让obj的指针指向e的后继节点
p.next = node;
size++;
return true;
}
@Override
public Object remove(int i) {
if (i >= size || i < 0) {
throw new RuntimeException("指针越界! " + i);
}
Node p = head;
// 找到索引i的前一个元素
for (int j = 0 ; j < i; j++) {
p = p.next;
}
Node node = p.next; // 索引i所在位置的元素
System.out.println(node.data);
// 将前一个元素的指针指向 索引i的后一个元素
p.next = p.next.next;
System.out.println(node);
size --;
return node;
}
@Override
public boolean remove(Object e) {
int i = indexOf(e);
if (i < 0 || i >= size) {
return false;
}
remove(i);
return true;
}
@Override
public Object replace(int i, Object e) {
if (i < 0 || i >= size) {
throw new RuntimeException("指针越界! " + i);
}
Node p = head;
for (int j = 0; j < i; j++) {
p = p.next;
}
// 将前一个元素的指针指向node
Node oldValue = p.next;
p.next.data = e;
return oldValue;
}
/*
单链表 :
数据, 指向后面节点的指针
*/
@Override
public String toString() {
if (size == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
Node p = head.next;
for (int i = 0; i < size; i++) {
if (i != size - 1) {
sb.append(p.data).append(",");
} else {
sb.append(p.data);
}
p = p.next;
}
sb.append("]");
return sb.toString();
}
}
后记: 有的时候真的是眼高手低,看起来很简单的东西
自己实践起来,却是漏洞百出,调试的心累~
总之,基础还不够扎实,动手能力也不够强
还是得多练习,多学习!!!
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)