链表的分类
链表分为：单链表，双向链表、单向循环链表
单链表
单链表添加实现思路
添加分为直接添加与指定位置添加
- 直接添加尾节点next指针直接指向新元素即可
- 指定位置添加需要一个辅助指针temp，如图
思路为：
- 首先找到指定节点位置
- 新节点的next指针指向辅助指针temp的下一个节点:node.next=temp.next
- 辅助指针temp的下一个节点指向新节点：temp.next=node
修改实现思路
找到临时指针temp直接修改里面的属性即可
删除思路
找到被删除节点的前一个节点，直接指向要删除节点的后一个节点即可
单链表代码实现
public class SingleLinkedListDemo {
public static void main(String[] args) {
Node node1 = new Node(1, "aaa");
Node node2 = new Node(2, "bbb");
Node node3 = new Node(3, "ccc");
Node node4 = new Node(4, "ddd");
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(node1);
singleLinkedList.add(node2);
singleLinkedList.add(node3);
singleLinkedList.add(node4);
singleLinkedList.delete(4);
Node node5 = new Node(3, "xxxx");
singleLinkedList.update(node5);
singleLinkedList.list();
}
}
class SingleLinkedList {
private Node head = new Node(0, "头结点");
public Node getHead() {
return head;
}
public void add(Node node) {
Node temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = node;
}
public void add(int no, Node node) {
Node temp = head;
while (true) {
if (temp.next == null) {//说明temp已经在链表的最后
throw new RuntimeException("该节点不存在");
}
if (temp.no == no) {//找到了指定位置
node.next = temp.next;
temp.next = node;
break;
}
temp = temp.next; //后移，遍历当前链表
}
}
public void update(Node node) {
if (head.next == null) {
System.out.println("链表为空~");
return;
}
Node temp = head.next;
while (true) {
if (temp == null) {
System.out.println("更新失败，该节点不存在");
break; //已经遍历完链表
}
if (temp.no == node.no) {
//找到了要修改的节点
temp.name = node.name;
break;
}
temp = temp.next;
}
}
public void delete(int no) {
Node temp = head;
while(true) {
if(temp.next == null) {
throw new RuntimeException("该节点不存在");
}
if(temp.next.no == no) {//找到的待删除节点的前一个节点temp
temp.next = temp.next.next;
break;
}
temp = temp.next; //temp后移，遍历
}
}
public void list() {
Node temp = head.next;
while(true) {
if(temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
public void reversalList(Node head) {
if (head.next == null || head.next.next == null) {
return;
}
Node cur = head.next;
Node next;
Node reverseHead = new Node(0, "头节点");
while (cur != null) {
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
//将原来的链表指向新创建的反序列表
head.next = reverseHead.next;
}
}
class Node {
public int no;
public String name;
public Node next;
public Node(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "no="+no+",name="+name;
}
}
双向链表
单链表与双向链表对比
- 单链表查找只能是一个方向
- 单链表删除需要辅助节点，双向链表可以自我删除
- 双向链表可以向前也可以向后遍历
双向链表实现思路
- 遍历同单向链表
- 添加一个新节点相对比单链表需要维护两个指针：temp.next=node;node.pre=temp;
- 修改同单链表
- 删除指定节点思路：
首先找到要删除的节点比如temp
公式为：temp.pre.next=temp.next;temp.next.pre=temp.pre
双向链表代码实现
class DoubleLinkedList {
private Node head = new Node(0, "头结点");
public Node getHead() {
return head;
}
public void add(Node node) {
Node temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = node;
node.pre = temp;
}
public void update(Node node) {
if (head.next == null) {
System.out.println("链表为空~");
return;
}
Node temp = head.next;
while (true) {
if (temp == null) {
System.out.println("更新失败，该节点不存在");
break; //已经遍历完链表
}
if (temp.no == node.no) {
//找到了要修改的节点
temp.name = node.name;
break;
}
temp = temp.next;
}
}
public void delete(int no) {
Node temp = head.next;
if (temp == null) {
throw new RuntimeException("这是个空链表");
}
while (true) {
if (temp.no == no) {//找到的待删除节点
temp.pre.next = temp.next;
if (temp.next != null) {//如果是最后一个节点可能空指针
temp.next.pre = temp.pre;
}
break;
}
temp = temp.next; //temp后移，遍历
}
}
public void list() {
Node temp = head.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
class Node {
public int no;
public String name;
public Node next;
public Node pre;
Node(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "no=" + no + ",name=" + name;
}
}
单向环形链表
使用单向环形列表解决约瑟夫环问题
实现思路
- 构造一个first指针指向第一个节点、last指针指向最后一个节点
- first与last指针移动k-1次，到编号为k的那个人位置
- first与last移动m-1次，输出first所在的节点
- 删除first所在的节点，公式为：first = first.next; last.next = first;
举例：
假如n=5,k=1,m=2依次输出为： 2->4->1->5->3
代码实现
public class Josepfu {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addNode(5);// 加入5个节点
circleSingleLinkedList.show();
System.out.println("*************************************");
circleSingleLinkedList.printNo(1, 2); // 2->4->1->5->3
}
}
class CircleSingleLinkedList {
private Node first = null;
public void addNode(int nums) {
if (nums < 1) {
System.out.println("nums的值不正确");
return;
}
Node cur = null; // 辅助指针，帮助构建环形链表
for (int i = 1; i <= nums; i++) {
Node node = new Node(i);
// 如果是第一个节点
if (i == 1) {
first = node;
first.next = first; // 构成环
cur = first; // 让cur指向第一个节点
} else {
cur.next = node;
node.next = first;
cur = node;
}
}
}
public void show() {
if (first == null) {
System.out.println("没有任何数据");
return;
}
Node cur = first;
while (true) {
System.out.printf("编号 %d \n", cur.no);
if (cur.next == first) {// 说明已经遍历完毕
break;
}
cur = cur.next;
}
}
/**
* k 表示从第k个开始数数
* m 表示数几下
*/
public void printNo(int k, int m) {
if (first == null || k < 1) {
System.out.println("参数输入有误， 请重新输入");
return;
}
//创建一个last节点指向环形链表的最后一个节点位置
Node last = first;
while (true) {
if (last.next == first) {
break;
}
last = last.next;
}
//移动到第k个节点的位置
for (int j = 0; j < k - 1; j++) {
first = first.next;
last = last.next;
}
while (true) {
if (last == first) { //说明圈中只有一个节点
break;
}
for (int j = 0; j < m - 1; j++) {
first = first.next;
last = last.next;
}
System.out.printf("节点%d出圈\n", first.no);
//这时将first指向的节点出圈
first = first.next;
last.next = first;
}
System.out.printf("最后出圈的编号%d \n", first.no);
}
}
class Node {
public int no;// 编号
public Node next; // 指向下一个节点,默认null
Node(int no) {
this.no = no;
}
@Override
public String toString() {
return "no=" + no;
}
}
转载：https://blog.csdn.net/jingyangV587/article/details/101210868
查看评论