Java模仿單鏈表和雙端鏈表數據構造的實例講授。本站提示廣大學習愛好者：（Java模仿單鏈表和雙端鏈表數據構造的實例講授）文章只能為提供參考，不一定能成為您想要的結果。以下是Java模仿單鏈表和雙端鏈表數據構造的實例講授正文
模仿單鏈表
線性表：
線性表（亦作次序表）是最根本、最簡略、也是最經常使用的一種數據構造。
線性表中數據元素之間的關系是一對一的關系，即除第一個和最初一個數據元素以外，其它數據元素都是首尾相接的。
線性表的邏輯構造簡略，便於完成和操作。
在現實運用中，線性表都是以棧、隊列、字符串等特別線性表的情勢來應用的。
線性構造的根本特點為:
1．聚集中必存在獨一的一個“第一元素”；
2．聚集中必存在獨一的一個 “最初元素” ；
3．除最初一個元素以外，均有 獨一的後繼(後件)；
4．除第一個元素以外，均有 獨一的先驅(前件)。
鏈表：linked list
鏈表是一種物理存儲單位上非持續、非次序的存儲構造，數據元素的邏輯次序是經由過程鏈表中的指針鏈接順序完成的
每一個數據項都被包括在“鏈結點”（Link）中。
鏈結點是一個類的對象，這類可叫做Link。鏈表中有很多相似的鏈結點，每一個Link中都中包括有一個對下一個鏈結點援用的字段next。
鏈表對象自己保留了一個指向第一個鏈結點的援用first。(若沒有first，則沒法定位)
鏈表不克不及像數組那樣(應用下標)直接拜訪到數據項，而須要用數據間的關系來定位，即拜訪鏈結點所援用的下一個鏈結點，爾後再下一個，直至拜訪到須要的數據
在鏈頭拔出和刪除的時光龐雜度為O(1)，由於只須要轉變援用的指向便可
而查找、刪除指定結點、在指定結點後拔出，這些操作都須要均勻都須要搜刮鏈表中的一半結點，效力為O(N)。
單鏈表：
以“結點的序列”表現線性表 稱作線性鏈表（單鏈表）
是一種鏈式存取的數據構造，用一組地址隨意率性的存儲單位寄存線性表中的數據元素。(這組存儲單位既可所以持續的，也能夠是不持續的)
鏈結點的構造：
寄存結點值的數據域data;寄存結點的援用 的指針域（鏈域）next
鏈表經由過程每一個結點的鏈域將線性表的n個結點按其邏輯次序鏈接在一路的。
每一個結點只要一個鏈域的鏈表稱為單鏈表（Single Linked List） ， 一個偏向, 只要後繼結節的援用
/**
* 單鏈表:頭插法 落後先出
* 將鏈表的右邊稱為鏈頭，左邊稱為鏈尾。
* 頭插法建單鏈表是將鏈表右端算作固定的，鏈表赓續向左延長而獲得的。
* 頭插法最早獲得的是尾結點
* @author stone
*/
public class SingleLinkedList<T> {
private Link<T> first; //首結點
public SingleLinkedList() {
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(T data) {// 拔出 到 鏈頭
Link<T> newLink = new Link<T>(data);
newLink.next = first; //新結點的next指向上一結點
first = newLink;
}
public Link<T> deleteFirst() {//刪除 鏈頭
Link<T> temp = first;
first = first.next; //變革首結點，為下一結點
return temp;
}
public Link<T> find(T t) {
Link<T> find = first;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
return find;
}
public Link<T> delete(T t) {
if (isEmpty()) {
return null;
} else {
if (first.data.equals(t)) {
Link<T> temp = first;
first = first.next; //變革首結點，為下一結點
return temp;
}
}
Link<T> p = first;
Link<T> q = first;
while (!p.data.equals(t)) {
if (p.next == null) {//表現到鏈尾還沒找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍歷
System.out.println("List (first-->last):");
Link<T> current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍歷
Link<T> p = first, q = first.next, t;
while (q != null) {//指針反向，遍歷的數據次序向後
t = q.next; //no3
if (p == first) {// 當為本來的頭時，頭的.next應當置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//下面輪回中的if裡，把first.next 置空了, 而當q為null不履行輪回時，p就為本來的最且一個數據項，反轉後把p賦給first
first = p;
displayList();
}
class Link<T> {//鏈結點
T data; //數據域
Link<T> next; //後繼指針，結點 鏈域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
list.insertFirst(33);
list.insertFirst(78);
list.insertFirst(24);
list.insertFirst(22);
list.insertFirst(56);
list.displayList();
list.deleteFirst();
list.displayList();
System.out.println("find:" + list.find(56));
System.out.println("find:" + list.find(33));
System.out.println("delete find:" + list.delete(99));
System.out.println("delete find:" + list.delete(24));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}
打印
List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList$Link@17dfafd1 List (first-->last): the data is 22 the data is 78 the data is 33 ----reverse---- List (first-->last): the data is 33 the data is 78 the data is 22
單鏈表:尾插法 、落後先出 ——若將鏈表的左端固定，鏈表赓續向右延長，這類樹立鏈表的辦法稱為尾插法。
尾插法樹立鏈表時，頭指針固定不動，故必需設立一個尾部的指針，向鏈表左邊延長，
尾插法最早獲得的是頭結點。
public class SingleLinkedList2<T> {
private Link<T> head; //首結點
public SingleLinkedList2() {
}
public boolean isEmpty() {
return head == null;
}
public void insertLast(T data) {//在鏈尾 拔出
Link<T> newLink = new Link<T>(data);
if (head != null) {
Link<T> nextP = head.next;
if (nextP == null) {
head.next = newLink;
} else {
Link<T> rear = null;
while (nextP != null) {
rear = nextP;
nextP = nextP.next;
}
rear.next = newLink;
}
} else {
head = newLink;
}
}
public Link<T> deleteLast() {//刪除 鏈尾
Link<T> p = head;
Link<T> q = head;
while (p.next != null) {// p的下一個結點不為空，q等於以後的p(即q是上一個，p是下一個) 輪回停止時，q等於鏈尾倒數第二個
q = p;
p = p.next;
}
//delete
q.next = null;
return p;
}
public Link<T> find(T t) {
Link<T> find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
return find;
}
public Link<T> delete(T t) {
if (isEmpty()) {
return null;
} else {
if (head.data.equals(t)) {
Link<T> temp = head;
head = head.next; //變革首結點，為下一結點
return temp;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表現到鏈尾還沒找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍歷
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍歷
Link<T> p = head, q = head.next, t;
while (q != null) {//指針反向，遍歷的數據次序向後
t = q.next; //no3
if (p == head) {// 當為本來的頭時，頭的.next應當置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//下面輪回中的if裡，把head.next 置空了, 而當q為null不履行輪回時，p就為本來的最且一個數據項，反轉後把p賦給head
head = p;
displayList();
}
class Link<T> {//鏈結點
T data; //數據域
Link<T> next; //後繼指針，結點 鏈域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>();
list.insertLast(33);
list.insertLast(78);
list.insertLast(24);
list.insertLast(22);
list.insertLast(56);
list.displayList();
list.deleteLast();
list.displayList();
System.out.println("find:" + list.find(56));
System.out.println("find:" + list.find(33));
System.out.println("delete find:" + list.delete(99));
System.out.println("delete find:" + list.delete(78));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}
打印
List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList2$Link@17dfafd1 List (head-->last): the data is 33 the data is 24 the data is 22 ----reverse---- List (head-->last): the data is 22 the data is 24 the data is 33
模仿雙端鏈表，以鏈表完成棧和隊列
雙端鏈表：
雙端鏈表與傳統鏈表異常類似.只是新增了一個屬性-即對最初一個鏈結點的援用rear
如許在鏈尾拔出會變得異常輕易，只需轉變rear的next為新增的結點便可，而不須要輪回搜刮到最初一個節點
所以有insertFirst、insertLast
刪除鏈頭時，只須要轉變援用指向便可；刪除鏈尾時，須要將倒數第二個結點的next置空，
而沒有一個援用是指向它的，所以照樣須要輪回來讀取操作
/**
* 雙端鏈表
* @author stone
*/
public class TwoEndpointList<T> {
private Link<T> head; //首結點
private Link<T> rear; //尾部指針
public TwoEndpointList() {
}
public T peekHead() {
if (head != null) {
return head.data;
}
return null;
}
public boolean isEmpty() {
return head == null;
}
public void insertFirst(T data) {// 拔出 到 鏈頭
Link<T> newLink = new Link<T>(data);
newLink.next = head; //新結點的next指向上一結點
head = newLink;
}
public void insertLast(T data) {//在鏈尾 拔出
Link<T> newLink = new Link<T>(data);
if (head == null) {
rear = null;
}
if (rear != null) {
rear.next = newLink;
} else {
head = newLink;
head.next = rear;
}
rear = newLink; //下次拔出時，從rear處拔出
}
public T deleteHead() {//刪除 鏈頭
if (isEmpty()) return null;
Link<T> temp = head;
head = head.next; //變革首結點，為下一結點
if (head == null) {
<span > </span>rear = head;
}
return temp.data;
}
public T find(T t) {
if (isEmpty()) {
return null;
}
Link<T> find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
if (find == null) {
return null;
}
return find.data;
}
public T delete(T t) {
if (isEmpty()) {
return null;
} else {
if (head.data.equals(t)) {
Link<T> temp = head;
head = head.next; //變革首結點，為下一結點
return temp.data;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表現到鏈尾還沒找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p.data;
}
public void displayList() {//遍歷
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍歷
if (isEmpty()) {
return;
}
Link<T> p = head, q = head.next, t;
while (q != null) {//指針反向，遍歷的數據次序向後
t = q.next; //no3
if (p == head) {// 當為本來的頭時，頭的.next應當置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//下面輪回中的if裡，把head.next 置空了, 而當q為null不履行輪回時，p就為本來的最且一個數據項，反轉後把p賦給head
head = p;
displayList();
}
class Link<T> {//鏈結點
T data; //數據域
Link<T> next; //後繼指針，結點 鏈域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
TwoEndpointList<Integer> list = new TwoEndpointList<Integer>();
list.insertLast(1);
list.insertFirst(2);
list.insertLast(3);
list.insertFirst(4);
list.insertLast(5);
list.displayList();
list.deleteHead();
list.displayList();
System.out.println("find:" + list.find(6));
System.out.println("find:" + list.find(3));
System.out.println("delete find:" + list.delete(6));
System.out.println("delete find:" + list.delete(5));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}
打印
List (head-->last): the data is 4 the data is 2 the data is 1 the data is 3 the data is 5 List (head-->last): the data is 2 the data is 1 the data is 3 the data is 5 find:null find:3 delete find:null delete find:5 List (head-->last): the data is 2 the data is 1 the data is 3 ----reverse---- List (head-->last): the data is 3 the data is 1 the data is 2
應用鏈表完成棧 ，用前插 單鏈表就可以完成，
本類采取雙端鏈表完成：
public class LinkStack<T> {
private TwoEndpointList<T> datas;
public LinkStack() {
datas = new TwoEndpointList<T>();
}
// 入棧
public void push(T data) {
datas.insertFirst(data);
}
// 出棧
public T pop() {
return datas.deleteHead();
}
// 檢查棧頂
public T peek() {
return datas.peekHead();
}
//棧能否為空
public boolean isEmpty() {
return datas.isEmpty();
}
public static void main(String[] args) {
LinkStack<Integer> stack = new LinkStack<Integer>();
for (int i = 0; i < 5; i++) {
stack.push(i);
}
for (int i = 0; i < 5; i++) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
}
for (int i = 0; i < 6; i++) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
stack.push(i);
}
for (int i = 5; i > 0; i--) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
}
for (int i = 5; i > 0; i--) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
}
}
}
打印
peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:0 pop:null ---- peek:1 peek:1 peek:1 peek:1 peek:1 pop:1 pop:2 pop:3 pop:4 pop:5
鏈表完成 隊列 用雙端鏈表完成：
public class LinkQueue<T> {
private TwoEndpointList<T> list;
public LinkQueue() {
list = new TwoEndpointList<T>();
}
//拔出隊尾
public void insert(T data) {
list.insertLast(data);
}
//移除隊頭
public T remove() {
return list.deleteHead();
}
//檢查隊頭
public T peek() {
return list.peekHead();
}
public boolean isEmpty() {
return list.isEmpty();
}
public static void main(String[] args) {
LinkQueue<Integer> queue = new LinkQueue<Integer>();
for (int i = 1; i < 5; i++) {
queue.insert(i);
}
for (int i = 1; i < 5; i++) {
Integer peek = queue.peek();
System.out.println("peek:" + peek);
}
for (int i = 1; i < 5; i++) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
queue.insert(i);
}
for (int i = 5; i > 0; i--) {
Integer peek = queue.peek();
System.out.println("peek2:" + peek);
}
for (int i = 5; i > 0; i--) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
}
}
}
打印
peek:1 peek:1 peek:1 peek:1 remove:1 remove:2 remove:3 remove:4 ---- peek2:5 peek2:5 peek2:5 peek2:5 peek2:5 remove:5 remove:4 remove:3 remove:2 remove:1
