代碼實現

package top.gldwolf.java.datastructure.linkedtable;/*** @author: Gldwolf* @email: ZengqiangZhao@sina.com* @date: 2020/4/15 12:39*//*** 線性表的鏈式存儲結構** @param <T> 存儲的數據類型*/ public class LinkedTable<T> {private Node head = new Node();private Node last; // 最后一個節點private int length = 1; // 初始值為 0，只有一個頭節點public LinkedTable() {}/*** 添加一個新的數據到表尾** @param data 新添加的數據* @return 成功返回 true，失敗返回 false*/public boolean add(T data) {Node<T> node = new Node<>(data);// 現在最后一個元素為新添加的元素if (head.next == null) { // 如果頭節點指針為空，則表示表中無數據，新添加的數據為第一個節點head.next = node; // 頭節點指向第一個節點} else { // 如果原來不是空表的話last.next = node; // 原來的最后一個元素指針指向新添加的元素}last = node; // 最后一個節點為新添加的數據length++;return true;}/*** 獲取指定索引位置的數據，通過遍歷實現** @param index* @return 該節點的數據* @throws Exception 當下標越界時拋出異常*/public T get(int index) throws Exception { // 下標從 1 開始if (index <= 0 || index >= length) { // 如果索引大于或等于表長度: 如果有一個數據，則表長度為 2，取索引大于或等于 2 的數據則拋出異常throw new Exception("下標越界");} else { // 如果索引不越界/*如果索引不越界，則會從頭開始遍歷數據，每循環一遍，游標 +1，得到游標所在節點的數據，當游標達到指定索引時，返回這個數據，并退出循環*/Node cursor = head;for (int i = 1; i <= index; i++) { // 遍歷數據，每執行一步獲取一個節點，當個數達到索引值時，返回這個節點的數據cursor = cursor.next;}return (T) cursor.getData();}}/*** 在指定位置插入數據* @param index 數據要插入的位置* @param data 要插入的數據* @return 成功返回 true，否則返回 false* @throws Exception*/public boolean insert(int index, T data) throws Exception {if (index < 1 || index > length) {throw new Exception("下標越界");} else if (index == length) { // 如果在最末尾插入數據Node node = new Node(data);last.next = node;last = node;} else if (index == 1) { // 如果放在第一個節點Node node = new Node(data);node.next = head.next;head.next = node;} else { // 如果不在最末尾插入數據Node node = new Node(data);Node cursor = head;for (int i = 1; i < index; i++) { // 通過 cursor 得到這個索引的前一個數據cursor = cursor.next;}node.next = cursor.next;cursor.next = node;}length ++;return true;}public boolean delete(int index) throws Exception {if (index < 1 || index > length) {throw new Exception("下標越界");} else if (index == 1) { // 如果刪除的為第 1 個節點head.next = head.next.next;} else if (index == length - 1) { // 如果刪除的是最后一個節點Node cursor = head;for (int i = 1; i < length; i++) { // 找到要刪的節點的前一個節點cursor = cursor.next;}cursor.next = null;} else { // 如果刪除其它節點Node cursor = head;for (int i = 1; i < index; i++) { // 找到要刪的節點的前一個節點cursor = cursor.next;}cursor.next = cursor.next.next;}length--;return true;}@Overridepublic String toString() {StringBuffer res = new StringBuffer();Node cursor = head;for (int i = 1; i < length; i++) {cursor = cursor.next;res.append(cursor.getData() + ", ");}return res.toString() + " length: " + (length - 1);} }class Node<N> {protected Node next; // 指向下一個 Node// private Node pre; // 指向上一個 Nodeprivate N data; // 用來存儲數據protected Node() {} // 僅用于創建頭節點public Node(N data) { // 用于添加后續數據節點this.data = data;}public N getData() {return data;} }

測試類

package top.gldwolf.java.datastructure.linkedtable;/*** @author: Gldwolf* @email: ZengqiangZhao@sina.com* @date: 2020/4/15 12:40*/public class LinkedTableDriver {public static void main(String[] args) throws Exception {LinkedTable<String> table = new LinkedTable<>();table.add("2");table.add("3");table.add("4");table.add("5");table.add("6");String s = table.get(5);System.out.println(s);table.insert(1, "1");System.out.println(table.get(1));System.out.println(table.get(5));table.insert(4, "9");System.out.println(table.get(4));System.out.println(table.toString());table.delete(4);System.out.println(table);table.delete(1);System.out.println(table);table.delete(5);System.out.println(table);table.add("6");System.out.println(table);System.out.println(table.get(5));System.out.println(table.get(3));table.delete(5);table.delete(3);System.out.println(table);} }

總結

以上是生活随笔為你收集整理的数据结构之线性表：单链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。