數據結構——鏈表

來自專欄 magic Java

public class LinkedList { /* * 節點 */ private static class Node { // 後繼指針 public Node next; // 數據 public int data; /* * 創建節點 */ public Node(int data) { this.data = data; } /* * 創建節點 */ public Node() { } } private Node head = null; // 頭節點 /* * 初始化鏈表 */ public LinkedList() { head = new Node(); } /* * 添加單個節點 */ public void add(Node n) { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = n; } /* * 添加單個節點到指定位置 */ public void add(int index, Node node) { // 首先判斷範圍 if (index < 1 || index > length() + 1) { System.out.println("插入節點位置不合法"); return; } Node temp = head; for (int i = 1; i < index; i++) { temp = temp.next; } // 中間插入的替換 node.next = temp.next; temp.next = node; } public int length() { Node temp = head; int counter = 0; while (temp.next != null) { temp = temp.next; counter++; } return counter; } // 清除鏈表 public void clear() { head = null; } // 刪除節點 public void remove(int index) { if (index < 1 || index > length() + 1) { System.out.println("刪除位置不合法"); return; } Node temp = head; for (int i = 1; i < index; i++) { temp = temp.next; } // 中間插入的替換 temp.next = temp.next.next; } // 遍歷鏈表 public void show() { Node temp = head; while (temp.next != null) { temp = temp.next; System.out.println(temp.data); } } // 排序 public void sort() { // 如果長度小於2直接返回 if (length() < 2) { return; } // 創建一個新的鏈表 LinkedList newList = new LinkedList(); // 取到新的鏈表頭節點 Node newTemp = newList.head; // 將新的鏈表節點挪到第一個數據處 newTemp = newTemp.next; // 當長度大於1時候繼續排序 for (int i = 0; i < length(); i++) { // 取到舊的鏈表頭節點 Node temp = this.head; // 獲取個最小值 int minData = Integer.MAX_VALUE; // 每次進行一次鏈表遍歷 for (int j = 0; j < length(); j++) { // 移動節點 temp = temp.next; // 得到較小值 if (temp.data < minData) { int t = minData; minData = temp.data; temp.data = t; } } // 將較小值賦給當前節點 newList.add(new Node(minData)); } // 將老的賦值給新的 this.head = newList.head; } public static void main(String[] args) { // 創建鏈表 LinkedList list = new LinkedList(); list.add(new Node(1)); list.add(new Node(2)); list.add(new Node(3)); list.add(1, new Node(4)); list.show(); list.sort(); list.show(); }}

推薦閱讀：