什么是链表
非连续、非顺序的存储结构(链式存储)
1.单链表
单链表可以看作是火车一样拼接。链表存储数据的同时也要存储下一个节点在什么位置
(1).单链表基本知识和使用
//一个节点
public class Node {
// 节点内容
int data;
// 下一个节点
Node next;
public Node(int data) {
this.data = data;
}
/* 版本1：为节点追加节点,向后找,一直找到它没有下一个节点此时再添加新的节点
public void append(Node node) {
this.next = node;
}
*/
/* 版本2(循环currentNode和nextNode的不断向后跳动)：为节点追加节点,向后找,一直找到它没有下一个节点此时再添加新的节点
public void append(Node node) {
当前节点currentNode
Node currentNode = this;
循环向后找
while(true) {
当前节点的下一个节点nextNode
Node nextNode = currentNode.next;
如果没有下一个节点，即下一个节点为null，此时的currentNode节点为最后一个节点
if(nextNode == null) {
break;
}
再把下一个节点赋给当前节点
currentNode = nextNode;
}
把需要追加的节点追加为currentNode的nextNode
currentNode.next = node;
}
*/
// 版本3(把节点对象自己返回去,可以无限向后追加，链式编程)：为节点追加节点,向后找,一直找到它没有下一个节点此时再添加新的节点
public Node append(Node node) {
//当前节点currentNode
Node currentNode = this;
//循环向后找
while(true) {
//当前节点的下一个节点nextNode
Node nextNode = currentNode.next;
//如果没有下一个节点，即下一个节点为null，此时的currentNode节点为最后一个节点
if(nextNode == null) {
break;
}
//再把下一个节点赋给当前节点
currentNode = nextNode;
}
//把需要追加的节点追加为currentNode的nextNode
currentNode.next = node;
return this;
}
// 获取下一个节点
public Node next() {
return this.next;
}
// 获得这个结点的内容
public int getData() {
return this.data;
}
// 判断当前节点是否为最后一个节点
public boolean isLast() {
return this.next() == null;
}
}
编写测试类Test对单链表进行测试
public class Test {
public static void main(String[] args) {
// 创建一些节点
Node n1 = new Node(11);
Node n2 = new Node(22);
Node n3 = new Node(33);
// 追加节点
n1.append(n2);
n2.append(n3);
// 输出n1下一个节点
System.out.println(n1.next().getData()); //输出结果：22
// 输出n1下下个节点
System.out.println(n1.next().next().getData()); //输出结果：33
Node n4 = new Node(44);
n1.append(n4); //此时的n4其实是追加到了n3的后面
System.out.println(n3.next().getData());//输出结果：44
Node n5 = new Node(55);
Node n6 = new Node(66);
//版本3的优势可以链式编程
n1.append(n5).append(n6);
System.out.println(n5.next().getData());//输出结果：66
// 测试isLast()方法判断是否为最后一个节点
System.out.println(n5.isLast());//输出结果：false
System.out.println(n6.isLast());//输出结果：true
}
}
(2)删除单链表的节点
删除不了当下节点，只能删除下一个节点
那怎么删除下一个节点呢？
只能通过将下下个节点赋给当下节点的下一个节点，这样的话就达到删除了下一个节点的效果
//删除单链表方法
public void remove() {
//当前节点currentNode
Node currentNode = this;
//真正删除后currentNode的下一个节点nextNode
Node nextNode = currentNode.next.next;
//nextNode赋值给currentNode的下一个节点，达到删除效果
currentNode.next = nextNode;
}补上输出链表节点数据的show()方法
//打印输出链表元素思路：循环currentNode跳动来输出currentNode.getData()的值
public void show() {
Node currentNode = this;
while(true) {
//判定条件：如果currentNode为空则跳出循环
if(currentNode == null) {
break;
}
System.out.print(currentNode.getData()+" ");
//实现跳动的关键地方把currentNode.next()赋值给currentNode实现不断向后跳动
currentNode = currentNode.next();
}
System.out.println();
}进行删除n3的下一个节点的操作
代码
?????????????????输出结果
?(3)往单链表插入节点
/*单链表指定位置插入节点思路： 比如已有n1,n2,n3,把新节点n4插入到n2的后面
* 需要弄一个tempNode 取得 n3的值
* Node tempNode = n2.next();
* n2.next = n4;
* n4.next = tempNode;
*/
public void insert(Node node) {
Node tempNode;
tempNode = this.next;
this.next = node;
node.next = tempNode;
}?在n2后面插入一个节点n7
代码
? ? ?输出结果
?2.循环链表
首节点和末节点被连接在一起的链表
?
(1).循环链表基本知识和使用
public class LoopNode {
//节点存储的数据
int data;
//循环链表的特别之处，单链表中是Node next;就可
LoopNode next = this;
public LoopNode(int data) {
this.data = data;
}
//返回下一个节点
public LoopNode next() {
return this.next;
}
//删除下一个节点
public void remove() {
//先取得下下个节点的值
LoopNode tempLoopNode = this.next.next;;
//下下个节点赋值下个节点,达成删除原下一个节点的效果
this.next = tempLoopNode;
}
//插入一个节点
public void insert(LoopNode loopNode) {
//tempLoopNode把下一个节点存起来
LoopNode tempLoopNode = this.next;
//把传进来的loopNode传给this.next
this.next = loopNode;
//传进来的loopNode的下一个节点为一开始存的原先的下一个节点
loopNode.next = tempLoopNode;
}
//获得节点的data值
public int getData() {
return this.data;
}
}
测试循环双链表
//测试双向循环链表
public class Test {
public static void main(String[] args) {
LoopNode l1 = new LoopNode(11);
LoopNode l2 = new LoopNode(22);
LoopNode l3 = new LoopNode(33);
LoopNode l4 = new LoopNode(44);
l1.insert(l2);
l2.insert(l3);
l3.insert(l4);
System.out.println(l3.next().getData()); //输出结果:44,即l4
System.out.println(l4.next().getData()); //输出结果:11,即l1
System.out.println(l1.next().getData()); //输出结果:22,即l2
System.out.println(l2.next().getData()); //输出结果:33,即l3
}
}
3.双向循环链表
首节点和末节点被连接在一起的链表，并且双向循环链表的节点不仅包含指向下一个节点的指针 (next)，还包含指向前一个节点的指针 (pre)
?(1)双向循环链表基本知识和使用
/*
* 实现双向循环链表
* 思路：在DoubleNode里面有指向下一个节点的next 和指向上一个节点的 pre
*/
public class DoubleNode {
// 存储节点的内容
int data;
// 下一个节点的地址
DoubleNode next = this;
// 上一个节点的地址
DoubleNode pre = this;
// 构造器初始化,形参赋值给data
public DoubleNode(int data) {
this.data = data;
}
// 获取下一个节点
public DoubleNode next() {
return this.next;
}
// 获取上一个节点
public DoubleNode pre() {
return this.pre;
}
// 获取节点的数据
public int getData() {
return this.data;
}
// 在节点后面插入一个节点
public DoubleNode after(DoubleNode afterNode) {
//暂存原当前节点的下一个节点
DoubleNode tempNode = this.next;
//进行当前节点后面插入节点的操作,即当前节点的下一个节点为新插入的afterNode节点
this.next = afterNode;
//插入后的afterNode的前一个节点为当前节点
afterNode.pre = this;
//原当前节点的下一个节点tempNode,现在是afterNode的下一个节点
afterNode.next = tempNode;
//现在tempNode的前一个节点为afterNode
tempNode.pre = afterNode;
//设为void也可以,这里返回插入节点的那个对象,
//是为了方便测试的时候用链式编程即n1.after(n2).after(n3)....这些
return afterNode;
}
}
测试循环双链表类
public class Test {
public static void main(String[] args) {
DoubleNode n1 = new DoubleNode(11);
DoubleNode n2 = new DoubleNode(22);
DoubleNode n3 = new DoubleNode(33);
DoubleNode n4 = new DoubleNode(44);
// n1.after(n2);
// n2.after(n3);
// n3.after(n4);
n1.after(n2).after(n3).after(n4);
System.out.println(n1.next().getData()); //n1的下一个节点n2
System.out.println(n1.next().next().getData()); //n1的下下个节点n3
System.out.println(n1.next().next().next().getData()); //n1的下下下个节点n4
System.out.println(n4.next().getData()); //n4的下一个节点n1
System.out.println(n1.pre().getData());//n1的前一个节点 n4
System.out.println(n4.pre().getData());//n4的前一个节点 n3
}
}