【数据结构链表（一）】一一一一单向链表
1、🍎 什么是单向链表
? 链表包含单链表，双向链表，循环链表等等。相对于线性表，添加，删除操作非常方便，因为不用移动大量的节点，只需要修改对应的前后节点指针即可。下面用一个具体实例来说明下这种结构。现在有一需求，是将具有不同编号，姓名，昵称的人添加到系统中。首先需要创建节点，既然是链表，节点除了基本信息也要加入下一节点指针，方便计算机在内存中查找。
? 单向链表是通过指针构建的列表，基本结构就是头节点+下一节点地址指针—>节点+下一节点地址指针—>尾节点。
2、🍌 概念
**单链表：**用一个指向后继元素的指针将具有线性关系的各个结点链接起来，并且最后一个节点的后继指针为空指针。
3、🍊 链表特点
- 获取数据麻烦，需要遍历查找，比数组慢
- 方便插入、删除
4、🎃 单向链表的实现原理
- 创建一个节点类，其中节点类包含两个部分，第一个是数据域（你到时候要往节点里面储存的信息），第二个是引用域（相当于指针，单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向下一个和上一个节点）
- 创建一个链表类，其中链表类包含三个属性：头结点、尾节点和大小，方法包含添加、删除、插入等等方法。
4.1 🌛 单向链表的实现类
public class Node {
public Object data;
public Node next;
public Node(Object e){
this.data = e;
}
}
4.2 🅱? 如何自己实现链表
4.2.1 1?? 创建一个节点类
💅:注意这里的类节点是创建链表类的一个内部类；
/**
* @author xiaoCoder
* @version 1.0
* @description: TODO 单向列表实现
* @date 2021/7/29 15:03
*/
private class Node {
private T data;// 数据信息
private Node next;// 下一节点的引用
public Node() {
}
public Node(T data) {
this.data = data;
}
// 添加节点
public void add(T data) {
if (this.next == null) {
this.next = new Node(data); // 如果当前节点为空就直接添加
} else {
this.next.add(data);
}
}
public T get(int index) {
if (ListDemoXiao.this.foot++ == index) {
return this.data;
} else {
return this.next.get(index);
}
}
public boolean contains(T data) {
if (this.data.equals(data)) {
return true;
} else {
if (this.next == null) {
return false;
} else {
return this.next.contains(data);
}
}
}
public void replace(T oldData, T newData) {
if (this.data.equals(oldData)) {
this.data = newData;
} else {
if (this.next == null) {
System.out.println("没有找到替换的元素！");
} else {
this.next.replace(oldData, newData);
}
}
}
public void remove(Node previous, T data) {
if (this.data.equals(data)) {
previous.next = this.next;
this.next = null;
ListDemoXiao.this.count--;
return;
} else {
if (this.next != null) {
this.next.remove(this, data);
} else {
return;
}
}
}
public void remove(Node previous, int index) {
if (ListDemoXiao.this.foot++ == index) {
previous.next = this.next;
this.next = null;
ListDemoXiao.this.count--;
}else {
this.next.remove(this,index);
}
}
}
4.2.2 2?? 创建链表类
package com.dataStructure;
/**
* @author xiaoCoder
* @version 1.0
* @description: TODO 单向列表实现
* @date 2021/7/29 15:03
*/
public class ListDemoXiao<T> {
public static void main(String[] args) {
ListDemoXiao<String> myList = new ListDemoXiao<>();
myList.add("111");
myList.add("222");
myList.add("333");
myList.add("444");
myList.add("555");
//System.out.println(myList.get(1));
//System.out.println(myList.contains("222"));
//myList.replace("222", "dasdsad");
//System.out.println(myList.get(1));
Object[] objects = myList.toArray();
for (Object object : objects) {
System.out.println(object.toString());
}
System.out.println("rrrrrrrrrrrrrrrrrrrrr");
//myList.remove("111");
//for (Object o : myList.toArray()) {
// System.out.println(o.toString());
//}
myList.remove(1);
for (Object o : myList.toArray()) {
System.out.println(o.toString());
}
}
private int foot; // 根节点索引的位置
private int count;// 链表的长度
private Node root;// 标识根节点
private class Node {
private T data;// 数据信息
private Node next;// 下一节点的引用
public Node() {
}
public Node(T data) {
this.data = data;
}
// 添加节点
public void add(T data) {
if (this.next == null) {
this.next = new Node(data); // 如果当前节点为空就直接添加
} else {
this.next.add(data);
}
}
// 根据索引获取数据
public T get(int index) {
if (ListDemoXiao.this.foot++ == index) {
return this.data;
} else {
return this.next.get(index);
}
}
// 查看链表中是否包含当前数据
public boolean contains(T data) {
if (this.data.equals(data)) {
return true;
} else {
if (this.next == null) {
return false;
} else {
return this.next.contains(data);
}
}
}
// 根据数据来替换对应的数据信息
public void replace(T oldData, T newData) {
if (this.data.equals(oldData)) {
this.data = newData;
} else {
if (this.next == null) {
System.out.println("没有找到替换的元素！");
} else {
this.next.replace(oldData, newData);
}
}
}
// 找到相同的node节点进行删除
public void remove(Node previous, T data) {
if (this.data.equals(data)) {
previous.next = this.next;
this.next = null;
ListDemoXiao.this.count--;
return;
} else {
if (this.next != null) {
this.next.remove(this, data);
} else {
return;
}
}
}
// 根据索引值删除对呀的node节点
public void remove(Node previous, int index) {
if (ListDemoXiao.this.foot++ == index) {
previous.next = this.next;
this.next = null;
ListDemoXiao.this.count--;
}else {
this.next.remove(this,index);
}
}
}
public boolean isEmpty() {
return (count == 0 || this.root == null);
}
// 往链表中加入数据
public void add(T data) {
if (this.isEmpty()) {
this.root = new Node(data);
} else {
this.root.add(data);
}
this.count++;
}
// 获取链表中指定索引上的数据
public T get(int index) {
if (this.isEmpty()) {
return null;
}
this.foot = 0;
return this.root.get(index);
}
public boolean contains(T data) {
if (this.isEmpty()) {
return false;
}
return this.root.contains(data);
}
public void replace(T oldData, T newData) {
if (this.isEmpty()) {
return;
}
this.root.replace(oldData, newData);
}
public Object[] toArray() {
if (this.isEmpty()) return null;
int count = this.count;
Object[] objects = new Object[count];
for (int i = 0; i < objects.length; i++) {
objects[i] = this.get(i);
}
return objects;
}
/**
* 根据传入的数值进行删除
*
* @param data
*/
public void remove(T data) {
if (this.isEmpty()) return;
if (this.root.data.equals(data)) {// 删除的正好是根节点
Node temp = this.root;
this.root = this.root.next;
temp.next = null;
this.count--;
return;
} else {
this.root.remove(this.root, data);
}
}
/**
* Delete based on the index
* @param index
*/
public void remove(int index) {
if (this.isEmpty()) {
return;
}
if (index < 0 || this.count <= index) {
return;
}
if (index == 0) {
Node temp = this.root;
this.root = this.root.next;
temp.next = null;
this.count--;
return;
} else {
this.foot = 0;
this.root.remove(this.root, index);
}
}
}