Java模擬單鏈表和雙端鏈表數(shù)據(jù)結構的實例講解
更新時間：2016年04月08日 08:53:28 作者：匆忙擁擠repeat
這篇文章主要介紹了Java模擬單鏈表和雙端鏈表數(shù)據(jù)結構的實例,注意這里的雙端鏈表不是雙向鏈表,是在單鏈表的基礎上保存有對最后一個鏈接點的引用,需要的朋友可以參考下
模擬單鏈表
線性表：
線性表（亦作順序表）是最基本、最簡單、也是最常用的一種數(shù)據(jù)結構。
線性表中數(shù)據(jù)元素之間的關系是一對一的關系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。
線性表的邏輯結構簡單，便于實現(xiàn)和操作。
在實際應用中，線性表都是以棧、隊列、字符串等特殊線性表的形式來使用的。
線性結構的基本特征為:
1．集合中必存在唯一的一個“第一元素”；
2．集合中必存在唯一的一個 “最后元素” ；
3．除最后一個元素之外，均有 唯一的后繼(后件)；
4．除第一個元素之外，均有 唯一的前驅(qū)(前件)。
鏈表：linked list
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的
每個數(shù)據(jù)項都被包含在“鏈結點”（Link）中。
鏈結點是一個類的對象，這類可叫做Link。鏈表中有許多類似的鏈結點，每個Link中都中包含有一個對下一個鏈結點引用的字段next。
鏈表對象本身保存了一個指向第一個鏈結點的引用first。(若沒有first，則無法定位)
鏈表不能像數(shù)組那樣(利用下標)直接訪問到數(shù)據(jù)項，而需要用數(shù)據(jù)間的關系來定位，即訪問鏈結點所引用的下一個鏈結點，而后再下一個，直至訪問到需要的數(shù)據(jù)
在鏈頭插入和刪除的時間復雜度為O(1)，因為只需要改變引用的指向即可
而查找、刪除指定結點、在指定結點后插入，這些操作都需要平均都需要搜索鏈表中的一半結點，效率為O(N)。
單鏈表：
以“結點的序列”表示線性表 稱作線性鏈表（單鏈表）
是一種鏈式存取的數(shù)據(jù)結構，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。(這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的)
鏈結點的結構：
存放結點值的數(shù)據(jù)域data;存放結點的引用 的指針域（鏈域）next
鏈表通過每個結點的鏈域?qū)⒕€性表的n個結點按其邏輯順序鏈接在一起的。
每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked List） ， 一個方向, 只有后繼結節(jié)的引用
/**
* 單鏈表:頭插法 后進先出
* 將鏈表的左邊稱為鏈頭，右邊稱為鏈尾。
* 頭插法建單鏈表是將鏈表右端看成固定的，鏈表不斷向左延伸而得到的。
* 頭插法最先得到的是尾結點
* @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) {//指針反向，遍歷的數(shù)據(jù)順序向后
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
}
//上面循環(huán)中的if里，把first.next 置空了, 而當q為null不執(zhí)行循環(huán)時，p就為原來的最且一個數(shù)據(jù)項，反轉后把p賦給first
first = p;
displayList();
}
class Link<T> {//鏈結點
T data; //數(shù)據(jù)域
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是下一個) 循環(huán)結束時，q等于鏈尾倒數(shù)第二個
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) {//指針反向，遍歷的數(shù)據(jù)順序向后
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
}
//上面循環(huán)中的if里，把head.next 置空了, 而當q為null不執(zhí)行循環(huán)時，p就為原來的最且一個數(shù)據(jù)項，反轉后把p賦給head
head = p;
displayList();
}
class Link<T> {//鏈結點
T data; //數(shù)據(jù)域
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
模擬雙端鏈表，以鏈表實現(xiàn)棧和隊列
雙端鏈表：
雙端鏈表與傳統(tǒng)鏈表非常相似.只是新增了一個屬性-即對最后一個鏈結點的引用rear
這樣在鏈尾插入會變得非常容易，只需改變rear的next為新增的結點即可，而不需要循環(huán)搜索到最后一個節(jié)點
所以有insertFirst、insertLast
刪除鏈頭時，只需要改變引用指向即可；刪除鏈尾時，需要將倒數(shù)第二個結點的next置空，
而沒有一個引用是指向它的，所以還是需要循環(huán)來讀取操作
/**
* 雙端鏈表
* @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 style="white-space:pre"> </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) {//指針反向，遍歷的數(shù)據(jù)順序向后
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
}
//上面循環(huán)中的if里，把head.next 置空了, 而當q為null不執(zhí)行循環(huán)時，p就為原來的最且一個數(shù)據(jù)項，反轉后把p賦給head
head = p;
displayList();
}
class Link<T> {//鏈結點
T data; //數(shù)據(jù)域
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
使用鏈表實現(xiàn)棧 ，用前插 單鏈表就能實現(xiàn)，
本類采用雙端鏈表實現(xiàn)：
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
鏈表實現(xiàn) 隊列 用雙端鏈表實現(xiàn)：
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
相關文章
在系統(tǒng)運行過程中，可能由于一些配置項的簡單變動需要重新打包啟停項目，這對于在運行中的項目會造成數(shù)據(jù)丟失，客戶操作無響應等情況發(fā)生，針對這類情況對開發(fā)框架進行升級提供yml文件實時修改更新功能，這篇文章主要介紹了SpringBoot動態(tài)更新yml文件2023-01-01
SpringCloud微服務調(diào)用丟失請求頭的問題及解決方案
在Spring Cloud 中微服務之間的調(diào)用會用到Feign,但是在默認情況下,Feign 調(diào)用遠程服務存在Header請求頭丟失問題,下面給大家分享SpringCloud微服務調(diào)用丟失請求頭的問題及解決方案,感興趣的朋友一起看看吧2024-02-02
Spring集成Web環(huán)境與SpringMVC組件的擴展使用詳解
這篇文章主要介紹了Spring集成Web環(huán)境與SpringMVC組件，它是一個MVC架構，用來簡化基于MVC架構的Web應用開發(fā)。SpringMVC最重要的就是五大組件2022-08-08
SpringBoot @ControllerAdvice 攔截異常并統(tǒng)一處理
這篇文章主要介紹了SpringBoot @ControllerAdvice 攔截異常并統(tǒng)一處理，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09
解決Spring Data Jpa 實體類自動創(chuàng)建數(shù)據(jù)庫表失敗問題
這篇文章主要介紹了解決Spring Data Jpa 實體類自動創(chuàng)建數(shù)據(jù)庫表失敗問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
idea安裝jerbel及文件上傳下載的實現(xiàn)示例
JRebel是一個Java開發(fā)工具,它是一款用于實時代碼重載的插件,本文主要介紹了idea安裝jerbel及文件上傳下載的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解下2023-09-09
elasticsearch索引index之Translog數(shù)據(jù)功能分析
這篇文章主要為大家介紹了elasticsearch索引index之Translog數(shù)據(jù)功能分析，主要分析translog的結構及寫入方式，有需要的朋友可以借鑒參考下2022-04-04
這篇文章主要介紹了詳解使用zxing庫生成QR-Code二維碼的相關資料,需要的朋友可以參考下2017-05-05
本篇文章是作者在學習了Java中的逃逸相關知識后的心得分享，一起跟著小編學習下。2018-02-02
這篇文章主要介紹了通過Session案例分析一次性驗證碼登錄,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2017-03-03