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