简洁笔记-Java数据结构基础(4.线性结构链表)

简洁笔记-Java数据结构基础(4.线性结构链表) 什么是链表

非连续、非顺序的存储结构(链式存储)

1.单链表

单链表可以看作是火车一样拼接。链表存储数据的同时也要存储下一个节点在什么位置

(1).单链表基本知识和使用

//一个节点
public class Node {
//	节点内容
	int data;
//	下一个节点
	Node next;
	
	public Node(int data) {
		this.data = data;
	}
	

	
	

	
//		版本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)往单链表插入节点

	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)双向循环链表基本知识和使用

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

	}
}