链表
一、链表(Linked List)介绍
链表是有序的列表，但是它在内存中式存储如下
1) 链表是以节点的方式来存储,是链式存储
2) 每个节点包含 data 域， next 域：指向下一个节点.
3) 如图：发现链表的各个节点不一定是连续存储.
4) 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
二、单链表
使用带head头的单向链表实现
源码: 单链表
1，思路
准备 1)首先定义node节点对象 2)采用SingleLinkedList进行管理 3)在SingleLinkedList中定义head节点为new Node(-1,"","") 遍历 1)定义临时节点temp=head.next 2)while(temp!= null){temp=temp.next}遍历并在其中打印temp 新增 1)定义一个临时节点temp记录到最后的位置 2)while(temp.next != null){temp=temp.next}移动指针 3)设置temp.next=node(新增的节点) 删除 1)定义临时节点temp=head，定义boolean flag为标识是否寻找到需要删除的节点 2)while(temp.next != null){temp=temp.next}移动指针，判断temp.next.no=no(输入的节点id)为删除节点的前一个节点并修改flag为删除 3)判定 flag标识是否找到删除节点，如果找到就执行temp.next=temp.next.next 修改 1)定义临时节点temp=head，定义boolean flag为标识是否寻找到需要修改的节点 2)while(temp.next != null){temp=temp.next}移动指针，判断temp.next.no==node.no(node为需要修改的节点)并修改flag为修改 3)判定 flag标识是否找到修改节点，如果找到就执行node.next=temp.next.next;temp.next=node
2，代码实现
/** * 添加节点 */ public void add(Node node) { Node temp = head; while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = node; } /** * 删除节点 */ public void del(int no) { //临时节点为需要删除节点的前一个节点 Node temp = head; boolean flag = true; //标识是否已经寻找完毕 while (true) { //如果已经遍历完毕 if (temp.next == null) { flag = false; break; } //找到需要删除节点的上一个节点 if (temp.next.no == no) { break; } temp = temp.next; } if (!flag) { System.out.println("找不到需要删除的节点!!!"); return; } //删除对应的节点 temp.next = temp.next.next; } /** * 修改节点 */ public void update(Node node) { //临时节点为需要修改节点的前一个节点 Node temp = head; //判断是否在链表中找到对应的节点 boolean flag = true; while (true) { //没有找到对应的节点 if (temp.next == null) { flag = false; break; } //找到对应的节点 if (temp.next.no == node.no) { break; } //后移 temp = temp.next; } if (!flag) { System.out.println("找不到需要修改的节点!!!"); return; } //修改 node.next = temp.next.next; temp.next = node; } /** * 遍历单链表 */ public void list(){ //第一个节点 Node temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.next; } }
View Code
3，单链表扩展(面试题)
思路
查找单链表中的倒数第k个节点 1)获取链表的长度(新方法)，采用临时变量count=0，定义临时变量temp=head.next;while(temp!=null){count++;temp=temp.next}，将最终的count返回 2)使用num=length-k(倒数第k个)，定义temp=head.next，flag=true 3)while(temp!= null){temp=temp.next}，将num--，当num==0时则break并且修改flag为找到对应节点 4)判断flag如果为找到状态，则直接返回当前的temp 反转单链表(改变链表结构) 1)定义一个新的头节点reverse，定义指针cur=head.next，定义临时节点temp=null 2)while(cur!=null){cur=cur.next}指针后移，指针后移之前先赋值temp=cur，然后将temp插入到reverse头节点和reverse.next节点之间 3)最后将原头节点的下一个节点指向新头节点的下一个节点，head.next = reverse.next 反向遍历(不改变链表结构) 1)定义栈Stack，定义临时节点temp=head.next 2)while(temp!=null){temp=temp.next}遍历，并将每个temp都push到栈 3)遍历栈，pop栈中的元素
代码
/** * 反向遍历 */ public void reversePrint() { //定义栈作为保存 Stack<Node> nodes = new Stack<>(); Node temp = head; while (true) { if (temp.next == null) { break; } nodes.push(temp.next); temp = temp.next; } while (!nodes.empty()) { System.out.println(nodes.pop()); } } /** * 反转（改变结构） */ public void reverse(){ //定义一个新的头节点 Node reverse = new Node(-1,"",""); //指针 Node cur = head.next; //临时变量为当前节点 Node temp = null; while (true) { if (cur == null) { break; } //当前值为指针指向的值 temp = cur; //指针后移 cur = cur.next; //当前节点为 头节点的下一个接待你 temp.next = reverse.next; //头节点的下一个节点为当前接待你 reverse.next = temp; } //将原始头节点下一个节点指向 新头节点的下一个节点 head.next = reverse.next; } /** * 查找单链表中的倒数第 k 个节点 */ public static Node getByNum(Node head,int num){ int k = getLength(head) - num; if (k < 0) { return new Node(-1,"k大于长度","-1"); } Node temp = head.next; //判断是否找不到 boolean flag = false; while (true) { if (temp == null) { break; } if (k == 0) { flag = true; break; } k--; temp = temp.next; } if (!flag) { //越界了，k为负数 return new Node(-1,"k为负数","-1"); } return temp; } /** * 求单链表中有效节点的个数 */ public static int getLength(Node head){ int count = 0; Node temp = head.next; while (true) { if (temp == null) { break; } count++; temp = temp.next; } return count; }
View Code
三、双向链表
源码：双向链表
1，思路
准备 1)首先定义node节点对象，存在next和pre两个属性 2)采用DoubleLinkedList进行管理 3)在DoubleLinkedList中定义head节点为new Node(-1,"","") 遍历 1)定义临时节点temp=head.next 2)while(temp!= null){temp=temp.next}遍历并在其中打印temp 新增 1)定义一个临时节点temp记录到最后的位置 2)while(temp.next != null){temp=temp.next}移动指针 3)设置temp.next=node(新增的节点)，node.pre=temp(双向关联) 删除(自我删除) 1)定义临时节点temp=head.next(需要被删除的节点)，定义boolean flag为标识是否寻找到需要删除的节点 2)while(temp!= null){temp=temp.next}移动指针，判断temp.no=no(输入的节点id)为删除节点，temp.pre.next=temp.next，如果temp.next不为空则temp.next.pre=temp.pre，并修改flag为删除 3)判定 flag标识是否找到删除节点 修改 1)定义临时节点temp=head.next，定义boolean flag为标识是否寻找到需要修改的节点 2)while(temp!= null){temp=temp.next}移动指针，判断temp.no==node.no(node为需要修改的节点)，修改temp的属性(或者修改next，pre指向)，并修改flag为修改,break 3)判定 flag标识是否找到修改节点，没找到给出提示
2，代码
private DoubleNode head = new DoubleNode(-1, "", ""); /** * 删除节点 */ public void delete(int no) { if (no <= 0) { System.out.println("删除节点的no不规范!!!"); return; } DoubleNode temp = head.next; boolean flag = false; while (temp != null) { if (temp.no == no) { temp.pre.next = temp.next; if (temp.next != null) { temp.next.pre = temp.pre; } flag = true; } temp = temp.next; } if (!flag) { System.out.println("需要被删除的节点不存在"); } } /** * 修改节点 */ public void update(DoubleNode node) { if (node == null || node.no <= 0) { System.out.println("被修改的节点不规范!!!"); return; } DoubleNode temp = head.next; boolean flag = false; while (temp != null) { if (temp.no == node.no) { temp.name = node.name; temp.nickname = node.nickname; /*node.next = temp.next; node.pre = temp.pre; temp.pre.next = node; if (temp.next != null) { temp.next.pre = node; }*/ flag = true; } temp = temp.next; } if (!flag) { System.out.println("找不到节点!!!"); } } /** * 添加节点 */ public void add(DoubleNode node) { DoubleNode temp = head; while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = node; node.pre = temp; } /** * 遍历节点 */ public void list() { DoubleNode temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.next; } }
View Code
四、环形链表(约瑟夫问题)
源码:环形链表
1，应用场景
Josephu 问题为： 设编号为 1， 2， … n 的 n 个人围坐一圈， 约定编号为 k（1<=k<=n） 的人从 1 开始报数， 数到 m 的那个人出列， 它的下一位又从 1 开始报数， 数到 m 的那个人又出列， 依次类推， 直到所有人出列为止， 由此产生一个出队编号的序列。
2，创建环形链表
思路
准备 1)提前创建CircleNode对象为定义的节点 2)定义CircleLinkedList为环形链表的管理类 3)在CircleLinkedList中定义CircleNode first = null，定义链表的第一个节点 添加 1)判定first==null，如果为空则是第一次添加，那么first=node，并且node.next=first 2)如果first节点不为空，定义temp=first节点，while(temp.next!=first){temp=temp.next}遍历后移至first节点的前一个节点。 3)将node节点加到temp节点后first节点前，temp.next=node并且node.next=first 遍历 1)定义temp=first，先打印first节点 2)while(temp.next!=first){temp=temp.next}打印temp.next
代码
/** * 遍历 */ public void show() { if (first == null) { System.out.println("当前链表为空链表!!!"); return; } CircleNode temp = first; System.out.printf("当前编号为%d\n", first.no); while (temp.next != first) { System.out.printf("当前编号为%d\n", temp.next.no); temp = temp.next; } } /** * 初始化环形队列 */ public void init(int num) { if (num < 1) { System.out.println("初始化环形链表小于1，失败!!!"); return; } for (int i = 1; i <= num; i++) { CircleNode circleNode = new CircleNode(i); add(circleNode); } } /** * 添加node */ public void add(CircleNode node) { if (node == null) { System.out.println("需要添加的节点不存在!!!"); return; } if (first == null) { first = node; node.next = first; } CircleNode temp = first; while (true) { if (temp.next == first) { break; } temp = temp.next; } temp.next = node; node.next = first; }
View Code
3，出圈
思路
1)获取环形链表的总长度 2)定义出圈的方法需要接收step步长和start开始位置 3)定义cur=first需要出圈的节点，定义pre=first出圈的前一个节点while(pre.next!=first){pre=pre.next} 4)for循环start次，同时移动cur=cur.next和pre=pre.next 5)while(cur.next!=cur){...cur=cur.next}移动cur指针。在while循环中增加for循环step-1次，每次将pre和cur都后移，那么移动完成之后设置pre.next=cur.next这样就会去除cur 6)留存的就是最后的cur
代码
/** * 出圈 * * @param step 步长 * @param start 开始的位置 */ public void out(int step, int start) { int length = getLength(); if (length < 1 || step < 1 || start > length) { System.out.println("参数不合规!"); return; } //定义需要出圈的节点 CircleNode cur = first; //需要出圈节点的前一个节点 CircleNode pre = first; while (pre.next != first) { pre = pre.next; } //开始的位置 for (int i = 0; i < start; i++) { pre = pre.next; cur = cur.next; } while (cur.next != cur) { for (int i = 0; i < step-1; i++) { pre = pre.next; cur = cur.next; } System.out.printf("出圈编号为:%d\n",cur.no); pre.next = cur.next; cur = cur.next; } System.out.printf("出圈编号为:%d\n",cur.no); } /** * 获取环形链表的长度 */ public int getLength() { if (first == null) { return 0; } int count = 1; CircleNode temp = first; while (temp.next != first) { count++; temp = temp.next; } return count; }
View Code
