链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
- 优点：无需处理固定容量的问题; 动态数据结构.
- 缺点：丧失随机访问的能力
单链表的具体实现
/**
* @create 2021-08-08 14:17
* 单链表的基本实现;
*/
public class MyLink<T> {
/**
* 创建节点内部类
*/
class Node {
//val 数据域;
private T val;
//next 指向下个结点的引用;默认指向空;
private Node next;
//初始化结点;
public Node(T val) {
this.val = val;
this.next = null;
}
//结点数据,输出方法;
@Override
public String toString() {
return this.val.toString();
}
}
//定义链表头;
private Node head;
//链表的实际结点个数;
private int size;
//初始化链表;
public MyLink() {
this.head = null;
this.size = 0;
}
/**
* 判断链表是否为空;
*/
public boolean isEmpty() {
return this.size == 0;
}
/**
* 获取链表的结点个数;
*/
public int getSize() {
return this.size;
}
/**
* 向链表尾部添加结点;
* @param val 添加的数据内容
*/
public void addTail(T val) {
//注意;向尾部插入结点时,由于索引index是从零开始的;那么这里直接向实际个数的位置插入结点;
add(val, this.size);
/*
为简化代码已注释;直接调用指定位置的添加方法-->add方法;
Node node = new Node(val);
//若链表为空时;直接就把这个插入的结点作为头结点;
if (head == null) {
head = node;
size++;
} else {
//将头结点的赋值给新结点;
Node curNode = head;
//判断后面是否还有结点;
while (curNode.next != null) {
curNode = curNode.next;
}
//最终把添加的结点赋值给新结点;即完成尾部添加;
curNode.next = node;
size++;
}*/
}
/**
* 向链表头部添加结点;
* @param val 添加的数据内容
*/
public void addHead(T val) {
add(val, 0);
/*
为简化代码已注释;直接调用指定位置的添加方法-->add方法;
Node node=new Node(val);
//让添加的结点作为头结点;
node.next = head;
head = node;
size++;*/
}
/**
* 向链表任意位置添加元素;
* @param val 添加的数据内容
* @param index 需要添加的位置;
*/
public void add(T val, int index) {
//判断输入的index是否超出当前链表范围;
if (index > this.size || index < 0) {
throw new IllegalArgumentException("index错误");
}
//创建需要添加的结点;
Node node = new Node(val);
//创建虚拟头结点;解决在头部添加结点的特殊处理;
Node dummyHead = new Node(null);
dummyHead.next = head;
Node preNode = dummyHead;
//这里最终preNode得到的是即将添加位置的结点;
for (int i = 0; i < index; i++) {
preNode = preNode.next;
}
//上面取到的(添加结点指向的下一个节点) ;赋值 到需要指定添加的结点的位置;
node.next = preNode.next;
//将指定添加结点的 放到指定位置;
preNode.next = node;
//结点个数增加;
this.size++;
//添加结点后,更新头结点;
head = dummyHead.next;
/* Node node = new Node(val);
//首先判断头结点;
if (head == null) {
head = node;
size++;
return;
}
//判断这个插入位置是不是头结点;
if (index == 0) {
node.next = head;
head = node;
size++;
return;
}
Node preNode = head;
for (int i = 0; i < index - 1; i++) {
preNode = preNode.next;
}
node.next = preNode.next;
preNode.next = node;
size++;*/
}
/**
* 输出链表;
*/
@Override
public String toString() {
StringBuilder sbl = new StringBuilder();
Node cur = head;
//排除头结点不为空的情况下,遍历得到所有结点;
while (cur != null) {
sbl.append(cur + "==>");
cur = cur.next;
}
sbl.append("null");
return sbl.toString();
}
/**
* 判断是否包含指定数据;
* @param val 指定的数据值;
*/
public boolean contains(T val) {
Node curNode = this.head;
//进行遍历链表,和指定的数据值进行比较;
while (curNode != null && !curNode.val.equals(val)) {
curNode = curNode.next;
}
return curNode != null;
}
/**
* 根据索引更新链表中的结点;
* @param index 指定的位置;
* @param val 指定设置的数据;
*/
public void set(int index, T val) {
if (index >= this.size || index < 0) {
throw new IllegalArgumentException("index错误");
}
Node curNode = head;
for (int i = 0; i < index; i++) {
curNode = curNode.next;
}
curNode.val = val;
}
/**
* 获取指定位置结点;
* @param index 指定的位置;
*/
public T get(int index) {
//判断输入的index是否超出当前链表范围;
if (index >= this.size || index < 0) {
throw new IllegalArgumentException("index错误");
}
Node curNode = head;
//遍历链表;
for (int i = 0; i < index; i++) {
curNode = curNode.next;
}
return curNode.val;
}
/**
* 获取头结点;
*/
public T getHead() {
return get(0);
}
/**
* 获取尾结点;
*/
public T getTail() {
return get(this.size - 1);
}
/**
* 删除头结点数据;
*/
public T removeHead() {
//索引位置为0时;
return remove(0);
/*
为简化代码已注释;直接调用指定位置的删除方法-->remove方法;
//判断头结点为空的情况;
if (head == null) {
return null;
}
//将下一个节点提到头结点位置;
head = head.next;
this.size--;
return head.val;*/
}
/**
* 删除尾结点数据;
*/
public T removeTail() {
return remove(this.size - 1);
/*
为简化代码已注释;直接调用指定位置的删除方法-->remove方法;
T result = null;
//判断头结点为空的情况;
if (head == null) {
return result;
}
//若只有一个结点时;头结点删除后为空;
if (this.size == 1) {
this.size--;
result = head.val;
head = null;
return result;
} else {
//新建一个结点作为标记点;
Node curNode = head;
//遍历链表;
for (int i = 0; i < this.size - 2; i++) {
curNode=curNode.next;
}
//取到最后一个结点的数据;
result=curNode.next.val;
curNode.next=null;
this.size--;
return result;
}*/
}
/**
* 删除指定位置的结点;
* @param index 要删除的索引位置;
*/
public T remove(int index) {
//判断输入的index是否超出当前链表范围;
if (index >= this.size || index < 0) {
throw new IllegalArgumentException("index错误");
}
//使用虚拟头结点（解决在头部删除结点的特殊处理)
Node dummyHead = new Node(null);
dummyHead.next = head;
//创建标记结点;
Node curNode = dummyHead;
//遍历指定索引前的结点;
for (int i = 0; i < index; i++) {
//将结点的下一个引用结点赋值给这个标记结点;
curNode = curNode.next;
}
//上面遍历时仅得到指定删除的上一个结点的值;这里获取到指定结点(需要删除)的值;
Node delNode = curNode.next;
T result = delNode.val;
//将删除结点后的下一个指向结点的,赋值到删除的结点位置;
curNode.next = delNode.next;
//使得这个被删除结点彻底脱离链表;
delNode.next = null;
//链表的结点个数变化;
this.size--;
//删除后更新头结点;
head = dummyHead.next;
return result;
}
}