站点图标

Java链表实现

2018-11-29折腾记录Java / 算法 / Develop
本文最后更新于 410 天前,文中所描述的信息可能已发生改变

转换阵营 ing,大部分的介绍都在注释写了,这里就不再重复了,注释中没有关于链表的原理,如果还不懂链表的可以先去看其他教程,这里不写主要是我比较懒( ̄ ▽  ̄)”

之前的算法有问题,现在已经修改完成,并重写了部分代码,对数据域使用泛型,可以存放任何对象了,存放不同数据类型时就不再需要定义多个链表类了ヾ(≧▽≦*)o

这个算法还有优化的空间,不久后将升级,心急的可以看 C 链表重置版然后将其改成 Java 即可


_247
package MyLinkedListDemo;
_247
_247
import java.util.Scanner;
_247
_247
public class MyLinkedListDemo {
_247
public static void main(String[] args) {
_247
Scanner in = new Scanner(System.in);
_247
MyLinkedList<Integer> list = new MyLinkedList<Integer>();
_247
list.add(-1, 1);
_247
list.add(-1, 2);
_247
list.add(-1, 3);
_247
list.add(-1, 4);
_247
list.add(-1, 5);
_247
int a = list.get(2);
_247
System.out.println(a);
_247
in.close();
_247
}
_247
}
_247
_247
class MyLinkedList<T> {
_247
_247
//链表总长度
_247
int len = 0;
_247
// 头节点
_247
Node head = null;
_247
// 尾节点
_247
Node end = null;
_247
_247
// 链表节点类(内部类)
_247
class Node {
_247
// 上一个节点
_247
Node prev;
_247
// 下一个节点
_247
Node next;
_247
// 数据块
_247
T data;
_247
_247
// 空构造器,用于构造临时节点和定位节点等不需要使用数据块的节点
_247
Node() {
_247
};
_247
_247
// 可填入数据的构造器,用填入数据
_247
Node(T data) {
_247
// 填入数据到数据块
_247
this.data = data;
_247
}
_247
}
_247
_247
// 插入链表节点的方法
_247
// 参数i : 表示要插入的位置,当 i = -1 时新节点会被放置头位置,若 i = -2 时新节点会被放置至尾位置
_247
public void add(int i /* 要添加的位置,新节点会添加至该位置之后 */, T data /* 传入数据 */) {
_247
// 递增定位
_247
len++;
_247
int j;
_247
// 定义定位节点
_247
Node indexNode = head;
_247
// 创建新节点
_247
Node newNode = new Node(data);
_247
_247
// 判断链表是否为空
_247
if (head == null) {
_247
// 若是只需将新节点设为头节点和尾节点就行
_247
head = newNode;
_247
end = newNode;
_247
return;
_247
}
_247
_247
// Create Mode
_247
if (i == -1) // 头插法
_247
{
_247
newNode.next = head;
_247
head.prev = newNode;
_247
head = newNode;
_247
return;
_247
} else if (i == -2) // 尾插法
_247
{
_247
while (indexNode.next != null) {
_247
indexNode = indexNode.next;
_247
}
_247
}
_247
_247
// Insert Mode
_247
_247
// 移动定位节点至指定位置
_247
for (j = 0; j < i && indexNode != null; j++) {
_247
indexNode = indexNode.next;
_247
}
_247
// 判断是否是添加至最后一个节点
_247
if (indexNode.next == null) {
_247
// 将上一个节点next指向新节点
_247
indexNode.next = newNode;
_247
// 将新节点的prev指向上一个节点
_247
newNode.prev = indexNode;
_247
// 将新节点的next指向null
_247
newNode.next = null;
_247
// 将新节点设为尾节点
_247
end = newNode;
_247
return;
_247
}
_247
// 创建临时节点用于存储原下一个节点的地址
_247
Node tempNode = indexNode.next;
_247
// 将上一个节点的next指向新节点
_247
indexNode.next = newNode;
_247
// 将新节点的next指向原下一个节点
_247
newNode.next = tempNode;
_247
// 将新节点的prev指向上一个节点
_247
newNode.prev = indexNode;
_247
// 将原下一个节点的prev指向新节点
_247
tempNode.prev = newNode;
_247
}
_247
_247
// 插入带数据的链表到指定位置,操作方式同add,只是新增的节点是已经有数据的
_247
public void add(int i, Node haveNode) {
_247
len++;
_247
int j;
_247
Node indexNode = head;
_247
_247
if (i == -1) {
_247
haveNode.next = head;
_247
head.prev = haveNode;
_247
head = haveNode;
_247
return;
_247
}
_247
_247
for (j = 0; j < i && indexNode != null; j++) {
_247
indexNode = indexNode.next;
_247
}
_247
_247
if (indexNode.next == null) {
_247
indexNode.next = haveNode;
_247
haveNode.prev = indexNode;
_247
haveNode.next = null;
_247
end = haveNode;
_247
return;
_247
}
_247
_247
haveNode.next = indexNode.next;
_247
haveNode.next.prev = haveNode;
_247
haveNode.prev = indexNode;
_247
indexNode.next = haveNode;
_247
}
_247
_247
// 删除指定节点
_247
// 参数 i : 当 i = 0 时代表删除第一个节点,i = -1 时代表删除最后一个节点
_247
public void delete(int i/* 要删除节点的位置 */) {
_247
len--;
_247
// 判断是否是删除第一个节点
_247
if (i == 0) {
_247
// 将头节点指向第二个节点,然后将头节点的prev设置为null,这样就屏蔽掉了第一个节点
_247
head = head.next;
_247
head.prev = null;
_247
return;
_247
}
_247
// 若是删除最后一个节点,那只需将尾节点移到倒数第二个节点即可
_247
else if (i == -1) {
_247
end = end.prev;
_247
end.next = null;
_247
return;
_247
}
_247
_247
// 递增定位
_247
int j;
_247
// 创建定位节点,将其指向头节点
_247
Node indexNode = head;
_247
// 将定位节点移至要删除节点的上一个节点
_247
for (j = 0; j < i - 1 && indexNode != null; j++) {
_247
indexNode = indexNode.next;
_247
}
_247
// 判断要删除节点是否是最后一个节点
_247
if (indexNode.next.next == null) {
_247
// 操作方式同删除头节点与
_247
end = end.prev;
_247
end.next = null;
_247
return;
_247
}
_247
// 要删除节点的下一个节点prev设置为要删除节点的上一个节点
_247
indexNode.next.next.prev = indexNode;
_247
// 将要删除节点的上一个节点的next设置为要删除节点的下一个节点
_247
indexNode.next = indexNode.next.next;
_247
}
_247
_247
// 清空链表
_247
public void clear() {
_247
len = 0;
_247
// 清空链表只需将头节点和尾节点设置为null即可,内存会由垃圾回收器回收
_247
head = null;
_247
end = null;
_247
}
_247
_247
// 遍历输出链表数据
_247
public void print() {
_247
// 创建定位节点
_247
Node indexNode = head;
_247
// 使用while循环进行遍历
_247
while (indexNode != null) {
_247
// 输出数据
_247
System.out.print(indexNode.data.toString() + " ");
_247
// 移动定位节点
_247
indexNode = indexNode.next;
_247
}
_247
// 换行
_247
System.out.println();
_247
}
_247
_247
// 链表逆置
_247
public void resever() {
_247
// 创建临时节点用来临时存储指向数据
_247
Node tempNode = new Node();
_247
// 将头节点与尾节点交换
_247
tempNode = head;
_247
head = end;
_247
end = tempNode;
_247
// 创建定位节点
_247
Node indexNode = head;
_247
// 循环交换next和prev数据
_247
while (indexNode.prev != null && (indexNode.next != null || indexNode == head)) {
_247
tempNode = indexNode.next;
_247
indexNode.next = indexNode.prev;
_247
indexNode.prev = tempNode;
_247
indexNode = indexNode.next;
_247
}
_247
// 设置最后一个节点的next为null
_247
end.next = null;
_247
// 设置最后一个节点的prev数据
_247
end.prev = tempNode.next;
_247
}
_247
_247
// 添加新节点到列表末尾
_247
public void addFirst(T data) {
_247
this.add(-2, data);
_247
}
_247
_247
// 添加新节点到列表头
_247
public void addLast(T data) {
_247
this.add(-1, data);
_247
}
_247
_247
// 获取指定位置的数据
_247
public T get(int i) {
_247
Node indexNode = head;
_247
for (int j = 0; j < i; j++) {
_247
indexNode = indexNode.next;
_247
}
_247
return indexNode.data;
_247
}
_247
_247
}

Java链表实现

https://blog.ixk.me/post/java-linked-list-implementation
  • 许可协议

    BY-NC-SA

  • 发布于

    2018-11-29

  • 本文作者

    Otstar Lin

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

图的搜索(遍历) - BFS & DFSC 快速排序