什么是鏈表
- 鏈表以節(jié)點的方式存儲, 是鏈式存儲
- 每個節(jié)點包含data域, next域, next指向下一個節(jié)點, 以此形成一條鏈
- 鏈表的各個節(jié)點不一定是連續(xù)存儲的
- 鏈表分帶頭節(jié)點和不帶頭節(jié)點
- 鏈表分為單鏈表和雙向鏈表
單向鏈表
-
單鏈表示意圖
帶頭節(jié)點的單鏈表示意圖 通過一個例子來認識單鏈表
如何使用帶頭單鏈表實現水滸英雄排行榜管理, 并對英雄任務進行增刪改查?
思路分析:
1.先創(chuàng)建一個頭節(jié)點, 不存放具體數據, 作用就是表示單鏈表的頭
2.每添加一個節(jié)點, 直接加到鏈表的最后
3.刪除節(jié)點, 需要先找到要刪除節(jié)點的前一個節(jié)點temp, 然后temp.next=temp.next.next即可, 被刪除的節(jié)點, 沒有引用指向它再扭， 會貝垃圾回收機制回收
3.怎么遍歷鏈表? 通過一個輔助變量, 幫助遍歷整個鏈表
/**
* 節(jié)點
*/
class HeroNode{
public int no;//英雄排名
public String name;//姓名
public String nickname;//昵稱
public HeroNode next; //指向下一個節(jié)點
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
/**
* 鏈表
*/
class SingleLinkedList{
//定義一個頭節(jié)點
private HeroNode head = new HeroNode(0, "", "");
/**
* 添加節(jié)點
* 思路:
* 1. 定義一個輔助變量, 遍歷鏈表到鏈表的尾部, 讓輔助變量指向鏈表的尾部節(jié)點
* 2. 添加節(jié)點到鏈表的尾部的next
* @param heroNode
*/
public void add(HeroNode heroNode){
//定義一個輔助節(jié)點
HeroNode temp = head;
//從head開始遍歷列表, 一直到鏈表的尾部
while (true){
if(temp.next == null){
break;
}
temp = temp.next; //temp后移
}
//這時temp就指向了鏈表的最后
temp.next = heroNode;
}
/**
* 根據編號來修改節(jié)點的信息
* 思路:
* 1. 定義一個輔助變量, 遍歷鏈表找到要更新的節(jié)點, 讓輔助變量指向要更新的節(jié)點
* 2. 找到就更新
* @param heroNode
*/
public void update(HeroNode heroNode){
//1. 判斷鏈表是否為空
if(head.next == null){
System.out.println("鏈表為空");
return;
}
//2. 找到要修改的節(jié)點
//2.1 定義一個輔助變量
HeroNode temp = head;
boolean flag = false; //標記下面循環(huán)中節(jié)點是否找到, 找到設為true
while (true){
if(temp == null){
break; //鏈表已經遍歷到尾部
}
if(temp.no == heroNode.no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}else {
System.out.println("沒有找到");
}
}
/**
* 刪除節(jié)點
* 思路:
* 1. 定義一個輔助節(jié)點變量, 遍歷鏈表, 讓輔助變量指向我們要刪除的節(jié)點的上一個節(jié)點
* 2. 然后temp.next = temp.next.next刪除節(jié)點
* @param no
*/
public void del(int no){
HeroNode temp = head;
boolean flag = false;
while (true){
if(temp.next == null){//遍歷完畢, 沒有找到
return;
}
if(temp.next.no == no){//找到
flag = true;
break;
}
temp = temp.next; // 后移
}
if(flag){
temp.next = temp.next.next;
}else{
System.out.println("沒有找到要刪除的節(jié)點");
}
}
/**
* 遍歷鏈表
*/
public void list(){
if(head.next == null){
System.out.println("鏈表為空");
return;
}
HeroNode temp = head.next;
while (true){
if (temp == null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
public class SingleLinkedDemo {
public static void main(String[] args) {
//1. 創(chuàng)建節(jié)點
HeroNode heroNode1 = new HeroNode(1, "宋江", "及時雨");
HeroNode heroNode2 = new HeroNode(2, "盧俊義", "玉麒麟");
HeroNode heroNode3 = new HeroNode(3, "吳用", "智多");
HeroNode heroNode4 = new HeroNode(4, "林沖", "豹子頭");
//2. 創(chuàng)建鏈表并添加節(jié)點
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(heroNode1);
singleLinkedList.add(heroNode2);
singleLinkedList.add(heroNode3);
singleLinkedList.add(heroNode4);
//3. 更新節(jié)點
singleLinkedList.update(new HeroNode(3, "吳用", "智多星"));
//4. 刪除節(jié)點
singleLinkedList.del(2);
//5.遍歷節(jié)點
singleLinkedList.list();
}
}
- 常見單鏈表面試題(代碼實現就不寫了)
- 求單鏈表有效節(jié)點的個數
思路分析: 定義一個變量count斥季，然后遍歷鏈表, 每遍歷一個就count++否过。 - 求單鏈表中倒數第k個節(jié)點(新浪面試題)
思路分析: 先遍歷鏈表, 得到鏈表的總長度length躏精，然后再遍歷鏈表, 獲取鏈表的第(length-k)個節(jié)點, 就是我們要的節(jié)點驮履。 - 單鏈表反轉(騰訊面試題)
思路分析: 先創(chuàng)建一個新的鏈表鱼辙，遍歷原來的鏈表, 每遍歷到一個就放到新的鏈表的最前面。 - 從尾到頭打印單鏈表(百度面試題, 要求方式, 1:反向遍歷; 2: Stack棧的方式)
思路1: 先反轉鏈表玫镐，然后遍歷即可倒戏。
思路2: 利用棧的數據結構, 將各個節(jié)點壓入到棧中, 然后利用棧的先進先出的特點, 實現逆序打印的效果。
棧的基本使用(參考)
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
//入棧
stack.add("zhangsan");
stack.add("lisi");
stack.add("王五");
//出棧
while (stack.size() > 0){
System.out.println(stack.pop());
}
}
雙向鏈表
- 單向鏈表和雙向鏈表的對比
1.單向鏈表, 只能查找一個方向, 雙向鏈表可以向前或向后查找
2.單項鏈表不能自我刪除, 需要依靠輔助節(jié)點, 雙向鏈表可以自我刪除 - 實際應用
需求:使用帶頭雙向鏈表實現水滸英雄排行榜管理, 并對英雄任務進行增刪改查恐似。
思路分析:
1.遍歷節(jié)點, 既可以向前, 也可以向后
2.添加節(jié)點, 先找到雙向鏈表的最后這個節(jié)點, 最后節(jié)點的next指向要添加的新節(jié)點, 新節(jié)點的pre指向最后節(jié)點
3.修改節(jié)點, 遍歷鏈表, 找到就修改該節(jié)點
4.刪除節(jié)點, 可以自我刪除, 加入要刪除的節(jié)點是temp, 則temp.pre.next=temp.next; temp.next.pre = temp.pre既可實現自我刪除
/**
* 節(jié)點
*/
class HeroNode{
public int no;//英雄排名
public String name;//姓名
public String nickname;//昵稱
public HeroNode next; //指向下一個節(jié)點
public HeroNode pre; //指向上一個節(jié)點
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
class DoubleLinkedList{
// 定義一個頭節(jié)點, 不存放任何數據, 也不要移動
private HeroNode head = new HeroNode(0, "", "");
/**
* 獲取頭節(jié)點
* @return
*/
public HeroNode getHead(){
return head;
}
/**
* 遍歷
*/
public void list(){
//判斷鏈表是否為空
if(head.next == null){
System.out.println("鏈表為空");
return;
}
//定義一個輔助變量
HeroNode temp = head.next;
while (true){
if(temp == null){
break;
}
System.out.println(temp);
temp = temp.next; //輔助變量后移
}
}
/**
* 添加一個節(jié)點
* @param heroNode
*/
public void add(HeroNode heroNode){
HeroNode temp = head;
while (true){
//鏈表的尾部
if(temp.next == null){
break;
}
temp = temp.next;
}
//形成一個雙向鏈表
temp.next = heroNode;
heroNode.pre = temp;
}
/**
* 更新節(jié)點
* @param heroNode
*/
public void update(HeroNode heroNode){
if(head.next == null){
System.out.println("鏈表為空");
return;
}
HeroNode temp = head.next;
boolean flag = false; //標記節(jié)點是否找到
while (true){
if(temp == null){
break;
}
if(temp.no == heroNode.no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}else {
System.out.println("沒有找到");
}
}
/**
* 刪除節(jié)點
* @param no
*/
public void del(int no){
if(head.next == null){
System.out.println("鏈表為空");
return;
}
HeroNode temp = head.next;
boolean flag = false; //標記節(jié)點是否找到
while (true){
if(temp == null){
break;
}
if(temp.no == no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.pre.next = temp.next;
//這個地方需要判斷一下, 是不是最后一個節(jié)點
if(temp.next != null){
temp.next.pre = temp.pre;
}
}else {
System.out.println("沒有找到");
}
}
}
環(huán)形鏈表
- 約瑟夫問題
編號為1,2...n的n個人圍成一個圈杜跷，從編號為k（0<=k<=n）的人從1開始報數，數到m的那個人出列矫夷，下一位重新從1開始報數葱椭，數到m的那個人出列，依次類推口四，直到所有人出列為止孵运，由此產生一個編號的序列。
思路分析:
先創(chuàng)建一個有n個節(jié)點的單循環(huán)鏈表蔓彩，然后由k節(jié)點從1開始計數治笨，到m時，把對應的節(jié)點從鏈表中刪除赤嚼，然后從刪除的節(jié)點的下一個節(jié)點開始從1開始計數旷赖，知道最后一個節(jié)點從鏈表中刪除。
class Boy{
//編號
private int no;
//指向下一個節(jié)點
private Boy next;
public Boy(int no) {
this.no = no;
}
//省略getter更卒、setter方法
}
class CircleSingleLinkedList{
//創(chuàng)建一個first節(jié)點, 沒有編號
private Boy first = null;
//創(chuàng)建鏈表
public void createBoyLinkedList(int nums){
if(nums < 1){
System.out.println("nums is error");
return;
}
Boy curBoy = null; //輔助指針
for(int i=1; i<=nums; i++){
//根據編號創(chuàng)建小孩
Boy boy = new Boy(i);
if(i==1){
first = boy;
first.setNext(first);
curBoy = first;
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
/**
* 遍歷鏈表
*/
public void showBoys(){
if(first == null){
System.out.println("空鏈");
return;
}
Boy curBoy = first;
while (true){
System.out.println("編號: "+curBoy.getNo());
if(curBoy.getNext() == first){
break;
}
curBoy = curBoy.getNext(); //后移
}
}
/**
* 計算小孩出圈順序
* @param k 第幾個小孩開始
* @param m 數幾下
* @param nums 有多少個小孩在圈里
*/
public void countBoy(int k, int m, int nums){
if(first == null || k<1 || k>nums || m<1){
System.out.println("數據有誤");
return;
}
Boy helper = first; //輔助指針
//1.輔助變量指向鏈表的最后這個節(jié)點
while (true){
if(helper.getNext() == first){
break;
}
helper = helper.getNext();
}
//2.讓first和helper移動k-1次
for(int i=0; i<k-1; i++){
first = first.getNext();
helper = helper.getNext();
}
//3.開始報數, first和helper同時移動m-1次, 然后出圈
while (true){
//只有最后一個小孩
if(helper == first){
break;
}
//讓first和helper指針同時移動m-1次
for(int j=0; j<m-1; j++){
first = first.getNext();
helper = helper.getNext();
}
System.out.println(first.getNo());
//這個時候first指向的小孩就是要出圈的小孩
first = first.getNext();
helper.setNext(first);
}
System.out.println(first.getNo());
}
}
# 測試
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.createBoyLinkedList(100);
//circleSingleLinkedList.showBoys();
circleSingleLinkedList.countBoy(10, 20, 100);
}
