//链表中数据的数据结构(节点)
private class Node {
T ele;
Node next; //指向下一个节点
//构造方法
public Node(T ele) {
this.ele = ele;
next = null;
}
public Node() {
this(null);
}
//重写Node toString ele是int属性的不影响,若是对象,就直接调用toString方法了
@Override
public String toString() {
return ele.toString();
}
}
3.初始化链表
size表示链表存储元素
定义链表的虚拟头结点
这个相当于null,实际不存在
虚拟头节点是解决在头部添加节点的特殊处理
链表的构造方法
创建一个长度为空的链表,虚拟头节点为空
//链表中存放元素的个数
private int size;
//链表的头 虚拟头节点(解决添加头结点问题)
private Node dummyHead;
//链表的数据结构
public MyLinked() {
size = 0;
dummyHead = new Node(null);
}
//获取链表中元素的个数
public int getSize() {
return size;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
4.链表的增
引用上述的头节点来解决添加头部元素问题,
若没有头结点,则遍历为0的位置添加头节点,只能添加到第二个位置,无法绑定,
在任意位置添加节点,
引入指针pre,重点也是找到待添加元素的前一个节点 pre
第一步先判断链表是否为空
创建一个新节点node,将待插入的值存入节点内
将指针pre指向虚拟头节点
然后开始遍历,找到待插入的节点的前一个节点(头节点)
node.next = pre.next; pre.next = node;
新节点的后继指向待插入节点的头节点的后继
待插入节点的头节点的后继指向新节点
注:
for (int i = 0; i < index; i++) { pre = pre.next; }
这里必须是小于index,只有小于 index才能确定是待插入节点的头节点
node.next = pre.next; pre.next = node;
顺序不能乱
顺序乱了,就变成待插入节点的头节点的后继指向新节点,新节点的后继指向自己了,就无法添加成功
//链表的头部增加节点
public void addHead(T ele) throws IllegalAccessException {
add(ele, 0);
}
//在任意位置添加节点 重点是找到待添加元素的前一个节点 pre
public void add(T ele, int index) throws IllegalAccessException {
if (index < 0 || index > size) {
throw new IllegalAccessException("index is error!!");
}
//创建一个新节点
Node node = new Node(ele);
Node pre = dummyHead;//待插入位置的前一个节点
//找到待插入节点的位置
for (int i = 0; i < index; i++) {
pre = pre.next;
}
node.next = pre.next;
pre.next = node;
size++;
}
//在尾部添加节点
public void addTail(T ele) throws IllegalAccessException {
add(ele, size);
}
5.链表遍历
实际就是输出,重写toString
创建一个新节点cur ,让他指向虚拟节点的后继(可以理解为是索引为0的节点)
在开始进行循环,如果cur节点的后继不是空,就一直添加,为空则跳出循环
//链表的遍历 也就是打印
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append("HEAD ");
//从头节点开始遍历
Node cur = dummyHead.next;//当前节点
while (cur != null) {
result.append(cur.ele + "--->");
if (cur.next == null) {
result.append("NULL");
}
cur = cur.next;
}
result.append(" TAIL");
return result.toString();
}
6.链表查询
根据索引查节点
创建一个新节点cur,让他指向虚拟节点的后继(可以理解为是索引为0的节点)
进行for循环,让其指向索引为index的节点
输出当前节点的值(cur.ele)即可
查询链表中是否包含指定的元素
创建一个新节点cur,让他指向虚拟节点
创建一个新节点node,让他指向节点cur
判断node节点的值和要查询包含的元素是否相同,相同则跳出循环
不相同则领cur的指针后移
若遍历结束还未找到直接返回false
//获取链表头元素
public T getHead() throws IllegalAccessException {
return get(0);
}
//获取链表尾结点
public T getTail() throws IllegalAccessException {
return get(size - 1);
}
//获取任意位置的节点(返回索引)
public T get(int index) throws IllegalAccessException {
if (index < 0 || index > size - 1) {
throw new IllegalAccessException("index is error!!");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.ele;
}
//查询链表中是否包含指定的元素
public boolean contains(T ele) {
Node cur = dummyHead;
while (cur.next != null) {
Node node = cur.next;
if (node.ele.equals(ele)) {
return true;
} else {
cur = cur.next;
}
}
return false;
}
//获取任意位置的节点(返回内容)
public Node getNode(int index) throws IllegalAccessException {
if (index < 0 || index > size - 1) {
throw new IllegalAccessException("index is error!!");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
}
7.链表更新
创建一个新节点cur ,让他指向虚拟节点的后继(可以理解为是索引为0的节点)
开始遍历,找到需要替换元素的索引,
将待插入元素赋值给当前节点即cur.ele = ele;
//更新节点内容
public boolean setNode(int index, T ele) throws IllegalAccessException {
if (index < 0 || index > size - 1) {
throw new IllegalAccessException("index is error!!");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.ele = ele;
return true;
}
8.链表删除
删除指定索引的元素
获取待删除元素的头节点prefix Node prefix = dummyHead; for (int i = 0; i < index; i++) { prefix = prefix.next; }
也就是获取到要删除节点的头一个节点prefix
获取到待删除的节点delNode Node delNode = getNode(index);
调用上述根据索引返回当前节点的方法delNode
也就是要删除的节点delNode
prefix.next = delNode.next; delNode.next = null;
删除节点的头节点的后继指向删除节点的后继(也就是要删除的节点的前一个指向要删除的后一个节点)
要删除的节点的后继指向空(相当于释放当前节点)
size–;当前链表的元素长度减一,
return delNode.ele;返回删除该节点的值
删除头节点,调用上述即可
删除尾节点不同
因为尾节点么有后继节点,所以无法调用上述方法
当也因此更加简单,直接找到尾节点的头节点指向空即可完成删除
注:
prefix.next = delNode.next; delNode.next = null;
顺序不能乱,乱了就相当于该节点指向空,一下子把后面全部节点都释放了
//待删除元素的头节点 Node prefix = dummyHead; for (int i = 0; i < index; i++) { prefix = prefix.next; }
这里 prefix 只能指向虚拟节点,若指向头结点则,查询索引就必须前移,for循环是从0开始的
i<index,不能等于,若等于则找到的不是要删除节点的头结点了就无法进行释放操作
//删除指定索引的元素
public T remove(int index) throws IllegalAccessException {
if (index < 0 || index > size - 1) {
throw new IllegalAccessException("index is error!!");
}
//待删除元素的头节点
Node prefix = dummyHead;
for (int i = 0; i < index; i++) {
prefix = prefix.next;
}
//获取到待删除的节点
Node delNode = getNode(index);
prefix.next = delNode.next;
delNode.next = null;
size--;
return delNode.ele;
}
//删除头节点
public T removeHead() throws IllegalAccessException {
return remove(0);
}
//删除尾节点
public T removeTail() throws IllegalAccessException {
//待删除元素的头节点
Node prefix = dummyHead;
for (int i = 0; i < size-1; i++) {
prefix = prefix.next;
}
T a = prefix.next.ele;
prefix.next = null;
size--;
return a;
}