鏈表定義
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構湾揽，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的瓤逼。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態(tài)生成库物。每個結點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域霸旗，另一個是存儲下一個結點地址的指針域。
鏈表的特點：
- 由于不必須按順序存儲戚揭，鏈表在插入的時候可以達到O(1)的復雜度诱告，比另一種線性表順序表快得多。
- 查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間
- 綜上民晒，插入速度快精居，查找速度慢。
- 使用鏈表結構可以克服數(shù)組鏈表需要預先知道數(shù)據(jù)大小的缺點镀虐，鏈表結構可以充分利用計算機內(nèi)存空間箱蟆。
鏈表的實現(xiàn)：
鏈表有很多種不同的類型：單向鏈表沟绪，雙向鏈表以及循環(huán)鏈表刮便。
本文代碼實現(xiàn)：Java代碼
- 通過內(nèi)部類定義了一個單向鏈表。
- 以鏈表為底層結構绽慈，實現(xiàn)了一個棧結構恨旱。
棧接口定義：
import java.util.Iterator;
/**
*
* @Created on 2017-02-15 8:40
* 棧結構定義辈毯，定義了基本的6種操作
*/
public interface FlowerStack<T> {
/**
* 壓棧
* @param item
*/
void push(T item);
/**
* 出棧
* @return
*/
T pop();
/**
* 棧的大小
* @return
*/
int size();
/**
* 棧是否為空
* @return
*/
boolean isEmpty();
/**
* 生成迭代器
*/
Iterator<T> iterator();
}
棧實現(xiàn)類代碼：
import java.util.Iterator;
/**
*
* @Created on 2017-02-15 19:12
* 基于鏈表的棧結構
*/
public class FlowerLinkedStack<T> implements FlowerStack<T> {
private Node<T> first; // 棧頂節(jié)點
private int length; // 元素數(shù)量
// 定義一個內(nèi)部類, 作為鏈表結構
private class Node<T> {
T item;
Node next;
}
@Override
public void push(T item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
length++;
}
@Override
public T pop() {
if (first == null) {
return null;
}
T item = first.item;
first = first.next;
length--;
return item;
}
@Override
public int size() {
return length;
}
@Override
public boolean isEmpty() {
return first == null;
}
@Override
public Iterator<T> iterator() {
return new FlowerLinkedStackIterator<T>();
}
/**
* 定義一個迭代器
* @param <K>
*/
private class FlowerLinkedStackIterator<K> implements Iterator<K> {
private Node it = first;
@Override
public boolean hasNext() {
return it != null;
}
@Override
public K next() {
K next = (K) it.item;
it = it.next;
return next;
}
@Override
public void remove() {
}
}
}
測試用例代碼：
import org.junit.Test;
import java.util.Iterator;
/**
*
* @Created on 2017-02-15 19:27
* 鏈表實現(xiàn)的棧結構 測試用例
*/
public class FlowerLinkedStackTest {
@Test
public void test() {
FlowerLinkedStack<Integer> stack = new FlowerLinkedStack();
System.out.println("初始尺寸：" + stack.size());
System.out.println("是否為空" + stack.isEmpty());
System.out.println(stack.pop());
for(int i=0; i<20; i++) {
stack.push(i);
System.out.println("當前尺寸：" + stack.size());
System.out.println("是否為空" + stack.isEmpty());
}
System.out.println("-----------------------------------------");
Iterator<Integer> iterator = stack.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("----------------------------------------");
for(int i=0; i<30; i++) {
System.out.println(stack.pop());
System.out.println("當前尺寸：" + stack.size());
System.out.println("是否為空" + stack.isEmpty());
}
}
}
