鏈表是一種遞回資料結構，它或者為空，或含有泛型元素的節點和指向另一節點的參考
通過嵌套類實作鏈表
private class Node {
Item item;
Node next;
}
Node作為鏈表中一個元素，保存一個泛型資料和下一個鏈表的參考，用例不會用到單獨Node，因而設為private
通過new Node() 建構式創建Node物件，呼叫結果是一個指向Node物件參考，實體變數初始為null，
通過把一個Node的next指向下一個元素可以實作鏈表，最后一個Node的next為null，
Node first = new Node();
Node second = new Node();
Node third = new Node();
first.item = "a";
second.item = "b";
third item = "c";
first.next = second;
second.next = third;
在表頭插入節點：
把first臨時保存，新建一個節點賦予first，其next值設定為原來的首節點，用時O(1)
在表頭洗掉節點
把first指向first.next，原來的first節點因為沒有參考，會被自動回收，用時O(1)
在表尾插入節點
保存指向尾節點的鏈接last，創建新的尾節點，把原來尾節點指向新節點，用時O(1)
其他位置的增刪
想要快速實作需要雙向鏈表，這里暫時不討論
鏈表堆疊的push方法首先保存原來的first，然后把first設定為新加入的node，并把該node的next指向原來的first
public void push(Item item) {
Node oldNode = first;
first = new Node();
first.item = item;
first.next = oldNode;
n++;
}
pop方法先保存現在的first，然后把first設定為first.next， 回傳保存的first
public Item pop() {
Item element = first.item;
first = first.next;
n--;
return element;
}
實作迭代器功能和之前的文章：使用陣列實作下壓堆疊 一樣
https://blog.csdn.net/Raine_Yang/article/details/119923848
完整代碼及測驗用例：
import java.util.Iterator;
public class LinkedListStack<Item> implements Iterable<Item> {
private class Node {
Item item;
Node next;
}
private int n = 0; //the length of stack
private Node first;
public boolean isEmpty() {
return n == 0;
}
public int size() {
return n;
}
public void push(Item item) {
Node oldNode = first;
first = new Node();
first.item = item;
first.next = oldNode;
n++;
}
public Item pop() {
Item element = first.item;
first = first.next;
n--;
return element;
}
public Iterator<Item> iterator() {
return new ReverseLinkedListIterator();
}
private class ReverseLinkedListIterator implements Iterator<Item> {
int i = 0;
Node current = first;
public boolean hasNext() {
return i > 0;
}
public Item next() {
Item element = current.item;
if (current.next != null) {
current = current.next;
}
return element;
}
public void remove() {
// Left blank on purpose
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedListStack<Integer> test = new LinkedListStack<Integer>();
test.push(1);
test.push(2);
test.push(3);
test.push(4);
test.push(5);
test.pop();
test.pop();
test.pop();
System.out.println(test.pop());
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296768.html
標籤：其他
上一篇：windows64位搭建匯編（包含匯編dosbox , masm檔案，link檔案和debug除錯）以及debug除錯命令（dosbox除錯匯編程式的簡單使用教程）
下一篇：資料結構與演算法總結