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)的引用,需要的朋友可以參考下
模擬單鏈表
線性表：
線性表（亦作順序表）是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。
線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。
線性表的邏輯結(jié)構(gòu)簡(jiǎn)單，便于實(shí)現(xiàn)和操作。
在實(shí)際應(yīng)用中，線性表都是以棧、隊(duì)列、字符串等特殊線性表的形式來(lái)使用的。
線性結(jié)構(gòu)的基本特征為:
1．集合中必存在唯一的一個(gè)“第一元素”；
2．集合中必存在唯一的一個(gè) “最后元素” ；
3．除最后一個(gè)元素之外，均有 唯一的后繼(后件)；
4．除第一個(gè)元素之外，均有 唯一的前驅(qū)(前件)。
鏈表：linked list
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?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。(若沒(méi)有first，則無(wú)法定位)
鏈表不能像數(shù)組那樣(利用下標(biāo))直接訪問(wèn)到數(shù)據(jù)項(xiàng)，而需要用數(shù)據(jù)間的關(guān)系來(lái)定位，即訪問(wèn)鏈結(jié)點(diǎn)所引用的下一個(gè)鏈結(jié)點(diǎn)，而后再下一個(gè)，直至訪問(wèn)到需要的數(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
鏈表通過(guò)每個(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) {//表示到鏈尾還沒(méi)找到
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) {//指針?lè)聪?，遍歷的數(shù)據(jù)順序向后
t = q.next; //no3
if (p == first) {// 當(dāng)為原來(lái)的頭時(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就為原來(lái)的最且一個(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) {//表示到鏈尾還沒(méi)找到
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) {//指針?lè)聪?，遍歷的數(shù)據(jù)順序向后
t = q.next; //no3
if (p == head) {// 當(dāng)為原來(lái)的頭時(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就為原來(lái)的最且一個(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置空，
而沒(méi)有一個(gè)引用是指向它的，所以還是需要循環(huán)來(lái)讀取操作
/**
* 雙端鏈表
* @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) {//表示到鏈尾還沒(méi)找到
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) {//指針?lè)聪?，遍歷的數(shù)據(jù)順序向后
t = q.next; //no3
if (p == head) {// 當(dāng)為原來(lái)的頭時(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就為原來(lái)的最且一個(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)文章
Spring Security OAuth2 token權(quán)限隔離實(shí)例解析
這篇文章主要介紹了Spring Security OAuth2 token權(quán)限隔離實(shí)例解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11
在現(xiàn)代的軟件開(kāi)發(fā)中,安全性是一個(gè)重要的考量因素,對(duì)于使用SpringBoot框架開(kāi)發(fā)的應(yīng)用程序而言,敏感信息如數(shù)據(jù)庫(kù)密碼、API密鑰等通常存儲(chǔ)在YAML配置文件中,而這些文件往往是明文存儲(chǔ),存在安全隱患,所以本文介紹了SpringBoot解決yml明文密碼問(wèn)題的方法2024-07-07
Idea如何導(dǎo)入java mysql驅(qū)動(dòng)包
本文介紹了如何在IntelliJ IDEA中配置MySQL數(shù)據(jù)庫(kù)連接,首先下載MySQL Connector/J驅(qū)動(dòng)并解壓,然后在Idea項(xiàng)目中創(chuàng)建lib文件夾并將.jar文件復(fù)制到該文件夾,接著,將.jar文件添加為項(xiàng)目庫(kù),通過(guò)這些步驟,可以成功配置MySQL數(shù)據(jù)庫(kù)連接2024-12-12
這篇文章主要介紹了Java中的類加載與類卸載方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12
Spring實(shí)現(xiàn)三級(jí)緩存機(jī)制
三級(jí)緩存機(jī)制是Spring解決循環(huán)依賴問(wèn)題的關(guān)鍵,本文主要介紹了Spring實(shí)現(xiàn)三級(jí)緩存機(jī)制,具有一定的參考價(jià)值,感興趣的可以了解一下2025-02-02
詳解Java中ByteArray字節(jié)數(shù)組的輸入輸出流的用法
ByteArrayInputStream和ByteArrayOutputStream分別集成自InputStream和OutputStream這兩個(gè)輸入和輸出流,這里我們就來(lái)詳解Java中ByteArray字節(jié)數(shù)組的輸入輸出流的用法,需要的朋友可以參考下2016-06-06
Java Socket實(shí)現(xiàn)聊天室附1500行源代碼
Socket是應(yīng)用層與TCP/IP協(xié)議族通信的中間軟件抽象層，它是一組接口。本篇文章手把手帶你通過(guò)Java Socket來(lái)實(shí)現(xiàn)自己的聊天室,大家可以在過(guò)程中查缺補(bǔ)漏，溫故而知新2021-10-10
這篇文章主要介紹了Java super關(guān)鍵字的使用方法詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家，讓大家對(duì)super關(guān)鍵字徹底掌握，需要的朋友可以參考下2017-10-10
這篇文章主要為大家詳細(xì)介紹了Java并發(fā)系列之ReentrantLock源碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-03-03
使用內(nèi)省相對(duì)于直接使用反射更加安全可靠，Java的反射機(jī)制比較特殊，它不同于一般的編程方式，稍不小心就容易破壞類的封裝性。練的不好，就容易走火入魔。沒(méi)關(guān)系，很多時(shí)候我們還可以使用Java的內(nèi)省機(jī)制哦2021-07-07