<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
Java資料結構之單連結串列的實現與面試題彙總
2022-10-26 14:02:39
1 單連結串列
1.1 單連結串列介紹
由於順序表的插入刪除操作需要移動大量的元素，影響了執行效率，因此引入了線性表的鏈式儲存——單連結串列。單連結串列通過一組任意的儲存單元來儲存線性表中的資料元素，不需要使用地址連續的儲存單元，因此它 不要求在邏輯上相鄰的兩個元素在物理位置上也相鄰。
物理結構示意圖：
邏輯結構示意圖：
關於單連結串列的一些說明：
- 連結串列是以節點的方式儲存的，每個節點包含data和next域，分別表示儲存的資料和指向下一個節點；
- 連結串列的各個節點不一定是連續儲存的；
- 可以根據實際需求來構造是否帶有頭節點的連結串列。
1.2 單連結串列的實現思路分析
1.2.1 單連結串列的建立與遍歷
單連結串列的建立：
先建立一個 head 頭節點，表示單連結串列的頭；
每新增一個節點就直接加入連結串列的最後；
遍歷的思路：
建立一個輔助指標，用於幫助遍歷整個連結串列；
當指標指向的節點的next域為null，說明當前節點為最後一個，遍歷完成。 1.2.2 單連結串列節點的插入與修改
示意圖如下：
- 首先需要通過遍歷找到需要新增節點的位置，圖中示意的為a1的位置；
- 新的節點的next指向a1.next；
- 將該位置，即a1.next指向新的節點。
修改操作相當於上述過程的簡化，只需要找到對應的節點直接修改節點對應的屬性即可，這裡不再贅述。
1.2.3 單連結串列節點的刪除
刪除序號為 “2” 的節點示意圖如下：
思路如下：
- 找到待刪除節點的前一個節點，範例中則找到序號為1的節點；
- 讓該節點的 temp.next = temp.next.next，即可；
- 由於被刪除的節點沒有其他的指向，則會由Java的垃圾回收機制進行回收，無需處理。
1.3 實現程式碼
StudentNode.java 節點類：
/**
* @author 興趣使然黃小黃
* @version 1.0
* 連結串列的節點類，包含學生資訊和next
*/
public class StudentNode {
public String no; //學號
public String name; //姓名
public int age; //年齡
public StudentNode next; //指向下一個節點
//構造器
public StudentNode(String no, String name, int age ){
this.no = no;
this.name = name;
this.age = age;
}
//為了顯示方便
@Override
public String toString() {
return "StudentNode{" +
"no='" + no + ''' +
", name='" + name + ''' +
", age=" + age +
'}';
}
}
StudentLinkedList.java 連結串列的實現類：
/**
* @author 興趣使然黃小黃
* @version 1.0
* 連結串列的實現類，用於管理眾多StudentNode節點
*/
public class StudentLinkedList {
//初始化頭節點
private StudentNode head = new StudentNode("", "", 0);
//獲取頭節點
public StudentNode getHead() {
return head;
}
//新增節點
//1.找到當前連結串列的最後節點
//2.將最後節點的next指向新的節點
public void add(StudentNode studentNode) {
StudentNode temp = head;
//遍歷連結串列找到最後的節點
while (temp.next != null) {
//沒有找到，就後移
temp = temp.next;
}
//最後的節點的next指向新節點
temp.next = studentNode;
}
//遍歷 顯示連結串列
public void showList(){
//判斷連結串列是否為空
if (head.next == null){
System.out.println("當前連結串列為空");
return;
}
//遍歷 使用輔助指標
StudentNode temp = head;
while (temp != null){
//更新指標
temp = temp.next;
if (temp.next == null){
System.out.print(temp);
break;
}
System.out.print(temp + "--->");
}
}
//插入節點
//根據學號順序查詢新增的位置, 如果存在, 則提示錯誤資訊
public void addByOrder(StudentNode studentNode){
//尋找的temp應該為新增位置的前一個節點
StudentNode temp = head;
boolean flag = false; //標識新新增的no是否已經存在
while (true){
if (temp.next == null){
//已經在連結串列的尾部
break;
}
if (Integer.parseInt(temp.next.no) > Integer.parseInt(studentNode.no)){
//位置找到 插入到temp後
break;
}else if (Integer.parseInt(temp.next.no) == Integer.parseInt(studentNode.no)){
//已經存在
flag = true;
break;
}
//移動指標
temp = temp.next;
}
if (flag){
System.out.println("n準備插入的學生資訊: " + studentNode.no + "，該學號已經存在，不可新增！");
}else {
studentNode.next = temp.next;
temp.next = studentNode;
}
}
//根據no學號修改學生資訊
public void update(StudentNode studentNode){
if (head.next == null){
System.out.println("當前連結串列為空, 無法修改");
return;
}
StudentNode temp = head.next;
boolean flag = false; //表示是否找到節點
while (true){
if (temp == null){
break;
}
if (temp.no == studentNode.no){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.name = studentNode.name;
temp.age = studentNode.age;
}else {
System.out.println("沒有找到");
}
}
//刪除節點
public void delete(String no){
StudentNode temp = head;
boolean flag = false; //標誌是否找到
//查詢到待刪除節點的前一個節點進行刪除操作
while (true){
if (temp.next == null){
//到達尾部
break;
}
if (temp.next.no == no){
//找到了
flag = true;
break;
}
//遍歷
temp = temp.next;
}
//刪除操作
if (flag){
temp.next = temp.next.next;
System.out.println("刪除成功！");
}else {
System.out.println("要刪除的節點不存在！");
}
}
}
測試類：
/**
* @author 興趣使然黃小黃
* @version 1.0
* 測試連結串列
*/
public class StudentListTest {
public static void main(String[] args) {
StudentNode node1 = new StudentNode("1", "黃小黃", 21);
StudentNode node2 = new StudentNode("2", "懶羊羊", 21);
StudentNode node3 = new StudentNode("3", "沸羊羊", 22);
//建立單連結串列 錄入資料 輸出
StudentLinkedList list = new StudentLinkedList();
list.add(node1);
list.add(node2);
list.add(node3);
System.out.println("遍歷連結串列:");
list.showList();
//測試插入資料方法
StudentNode node5 = new StudentNode("5", "美羊羊", 19);
StudentNode node4 = new StudentNode("4", "暖羊羊", 19);
list.addByOrder(node5);
list.addByOrder(node4);
System.out.println("n依次插入學號為5、4的學生後:");
list.showList();
//測試修改方法
System.out.println("n測試修改方法:");
list.update(new StudentNode("1", "禰豆子", 10));
list.showList();
//測試刪除方法
System.out.println("n測試刪除方法:");
list.delete("1");
list.delete("5");
list.showList();
}
}
實現結果：
遍歷連結串列:
StudentNode{no='1', name='黃小黃', age=21}--->StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}
依次插入學號為5、4的學生後:
StudentNode{no='1', name='黃小黃', age=21}--->StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
測試修改方法:
StudentNode{no='1', name='禰豆子', age=10}--->StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
測試刪除方法:
刪除成功！
刪除成功！
StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}
Process finished with exit code 0
2 單連結串列的面試題
2.1 統計單連結串列中有效節點數量
/**
*
* @param head 頭節點
* @return 返回有效節點個數
*/
public static int getLength(StudentNode head){
if (head.next == null){
return 0;
}
int length = 0;
StudentNode temp = head.next;
while (temp != null){
length++;
temp = temp.next;
}
return length;
}
2.2 新浪–倒數第k個節點
查詢連結串列中倒數第k個節點
思路分析：
- 編寫一個方法，接收head頭節點和index，index表示k；
- 連結串列從頭到尾遍歷，求出長度（連結串列節點個數）size；
- 從第一個節點，遍歷size-length次，即可找到倒數第k個節點。
參考程式碼：
/**
* 獲取單連結串列中倒數第k個節點
* @param head 連結串列的頭節點
* @param index 倒數第 k 個元素
* @return 返回倒數第 k 個元素，或者 null
*/
public static StudentNode findLastIndexNode(StudentNode head, int index){
//如果連結串列為空
if (head.next == null){
return null;
}
//得到連結串列的長度(節點個數)
int size = getLength(head);
//遍歷 size-index次 得到倒數第index個節點
//資料校驗
if (index <= 0 || index > size){
return null;
}
//遍歷
StudentNode current = head.next;
for (int i = 0; i < size - index; i++) {
current = current.next;
}
return current;
}
2.3 騰訊–單連結串列的反轉
反轉單連結串列
思路分析：
- 可以使用頭插法；
- 以原連結串列為模板，每遍歷一個節點，取出，並接在新連結串列的最前端；
- 原head頭節點，指向新的節點；
- 直到遍歷完為止。
參考程式碼：
/**
* 頭插法反轉連結串列
* @param head 接收待反轉的連結串列
* @return 返回一個反轉後的新連結串列
*/
public static StudentLinkedList reverseList(StudentNode head){
if (head.next == null){
return null;
}
StudentNode old = head.next; //用於遍歷舊連結串列
//建立新連結串列，新連結串列根據原連結串列遍歷得到
StudentLinkedList newList = new StudentLinkedList();
StudentNode newHead = newList.getHead(); //新連結串列的頭節點
//遍歷構造
boolean flag = true; //標記是否為第一次新增
while (old != null){
//頭插法加入到新連結串列中
StudentNode newNode = new StudentNode(old.no, old.name, old.age);
if(flag){
newHead.next = newNode;
newNode.next = null;
flag = false;
}else {
newNode.next = newHead.next;
newHead.next = newNode;
}
old = old.next;
}
return newList;
}
以上方式雖然可以實現連結串列的反轉，但是是以返回一個新的反轉連結串列的形式，並沒有真正意義上實現原地反轉，下面介紹另一種方式：
雙指標:
/**
* 雙指標就地反轉連結串列
* @param head 接收連結串列的頭節點，方法中會將連結串列反轉
*/
public static void reverse(StudentNode head){
//如果當前連結串列為空 或者只有一個節點 直接返回即可
if (head.next == null || head.next.next == null){
return;
}
//輔助指標遍歷原來的連結串列
StudentNode cur = head.next; //當前節點
StudentNode next = null; //指向cur的下一個節點
StudentNode reverseHead = new StudentNode("", "", 0);
//遍歷原來的連結串列，每遍歷一個節點，就取出，放在新連結串列的最前端
while (cur != null){
next = cur.next; //暫時儲存當前節點的下一個節點
cur.next = reverseHead.next; //講cur下一個節點放在連結串列最前端
reverseHead.next = cur;
cur = next; //cur後移動
}
head.next = reverseHead.next;
return;
}
2.4 百度–逆序列印單連結串列
從尾到頭列印單連結串列
方式一： 先將單連結串列反轉，然後再列印。但是這樣會破壞掉原有單連結串列的結構，而題目要求僅僅是列印，因此不建議！
方式二： 利用棧模擬
將單連結串列的各個節點壓入棧中，利用棧先進後出的特點，實現逆序列印。
參考程式碼：
/**
* 利用棧模擬 實現連結串列的逆序列印
* @param head 連結串列的頭節點
*/
public static void reversePrintList(StudentNode head){
if (head.next == null){
return; //空連結串列無法列印
}
//建立棧模擬逆序列印
Stack<StudentNode> stack = new Stack<>(); //棧
StudentNode cur = head.next;
//將連結串列的所有節點壓入棧
while (cur != null){
stack.push(cur);
cur = cur.next;
}
//逆序列印
while (!stack.empty()){
//出棧
System.out.println(stack.pop());
}
return;
}
以上就是Java資料結構之單連結串列的實現與面試題彙總的詳細內容，更多關於Java單連結串列的資料請關注it145.com其它相關文章！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45