文章目錄
- 節點類
- 鏈表類（主要）
- 測驗類
- 小結
節點類
可以根據需要，對節點屬性進行修改，注意重寫toString()方法，以便后續的輸出操作，
//節點類
class Node {
public int id;
public String name;
public Node next;
public Node(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Node{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
鏈表類（主要）
所實作的增刪改查，反轉，逆序等功能基本能適用，實作思路在代碼中注釋，
//鏈表類（管理節點）
class LinkedList {
//頭節點
Node head = new Node(0,null);
//鏈表有效資料個數（鏈表長度）（頭節點不計）
public int size(){
Node temp = head;
int size = 0;
while (true){
if (temp.next == null){
break;
}
size++;
temp = temp.next;
}
return size;
}
//展示鏈表
public void list(){
if (head.next == null){
System.out.println("鏈表為空！");
return;
}
Node temp = head.next;
while (true){
if (temp == null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
//增(根據id從小到大)
public void add(Node newNode){
Node temp = head;
while (true){ //用來找到鏈表尾
if (temp.next == null) {
break;
}
if (temp.id == newNode.id){
System.out.println("要添加的節點的id已經存在，添加失敗！");
return;
}
if (temp.next.id > newNode.id){
break;
}
temp = temp.next;
}
Node node = newNode;
newNode.next = temp.next;
temp.next = node;
}
//刪(根據id匹配洗掉)
public void remove(int id){
if (head.next == null){
System.out.println("鏈表為空!");
return;
}
Node temp = head;
boolean flag = false; //用來標記是否找到對應id的節點
while (true){
if (temp.next == null){
break;
}
if (temp.next.id == id){ //找到要洗掉節點的前一個節點
flag =true;
break;
}
temp = temp.next;
}
if (flag){
temp.next = temp.next.next;
}else {
System.out.println("沒有找到要洗掉的節點，洗掉失敗!");
}
}
//改（根據id匹配要修改的節點）
public void update(int id,String name){
if (head.next == null){
System.out.println("鏈表為空！");
return;
}
Node temp = head;
boolean flag = false; //用來標記是否找到對應id的節點
while (true){
if (temp.next == null){
break;
}
if (temp.id == id){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.name = name;
}else {
System.out.println("沒有找到要修改的節點，修改失敗！");
}
}
//查（根據id匹配）
public Node show(int id){
if (head.next == null){
System.out.println("鏈表為空！");
return null;
}
Node temp = head.next;
boolean flag = false;
while (true){
if (temp == null){
break;
}
if (temp.id == id){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
return temp;
}else {
System.out.println("沒有找到要查找的節點，查找失敗！");
return null;
}
}
//查找倒數第n個節點
public Node lastShow(int n){
Node temp = head.next;
int size = this.size();
if (size < n || n <= 0){
System.out.println("查找的節點不存在！");
return null;
}
for (int i = 0; i < size - n; i++) {
temp = temp.next;
}
return temp;
}
//鏈表反轉
public void reverse(){
if (head.next == null || head.next.next == null){
return;
}
Node reverseHead = new Node(0,null);
Node cur = head.next; //記錄當前遍歷到的節點
Node next = null; //記錄當前遍歷到的節點的下一個節點
while (true){
if (cur == null){ //確保遍歷到最后一個
break;
}
next = cur.next; //保存下一個節點，避免斷鏈
//使得反轉頭節點指向遍歷到的當前節點，而讓遍歷到的當前節點指向反轉頭節點的下一個節點
// 確保遍歷到的當前節點始終位于反轉頭節點的下一個
cur.next = reverseHead.next;
reverseHead.next = cur;
//遍歷
cur = next;
}
head.next = reverseHead.next; //最后讓原頭節點指向反轉頭節點的下一個節點，即可實作原鏈表的反轉
}
//逆序列印
//方法一：先反轉
//方法二：使用堆疊結構
public void reversePrint(){
if (head.next == null){
System.out.println("鏈表為空！");
return;
}
Stack<Node> nodes = new Stack<>();
Node temp = head.next;
while (true){
if (temp == null){
break;
}
nodes.push(temp);
temp = temp.next;
}
while (nodes.size() > 0){
System.out.println(nodes.pop());
}
}
}
測驗類
import java.util.Stack;
/**
* @Author: Yeman
* @Date: 2021-10-14-12:55
* @Description:
*/
//測驗類
public class SingleLinkedListTest {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
Node node1 = new Node(1, "阿蘭");
Node node2 = new Node(2, "洛國富");
Node node3 = new Node(3, "艾克森");
//可以不按照id順序添加
linkedList.add(node1);
linkedList.add(node3);
linkedList.add(node2);
linkedList.list();
System.out.println(linkedList.size()); //鏈表長度
// System.out.println(linkedList.lastShow(2)); //倒數查找
// linkedList.update(2,"張玉寧"); //改
//
// linkedList.remove(3); //刪
//
// System.out.println(linkedList.show(2)); //查
// linkedList.reverse(); //鏈表反轉
linkedList.reversePrint(); //逆序列印
}
}
小結
單鏈表的節點由具體資料域和指標域兩部分組成，而帶有頭節點的單鏈表的頭節點不存盤具體資料，其指標域則指向鏈表的第一個有效節點，即非頭節點的第一個節點，
當對單鏈表進行增刪改查，逆序等操作時，要定義一個Node型別的輔助變數來遍歷鏈表，而頭節點注意要保持不動，
進行反轉操作時，最后需要使得頭節點指向反轉后的鏈表的第一個節點，這是唯一一處使得頭節點變動的地方，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/316629.html
標籤：其他