一、單鏈表

1、在我們數(shù)據(jù)結(jié)構(gòu)中，單鏈表非常重要。它里面的數(shù)據(jù)元素是以結(jié)點(diǎn)為單位，每個(gè)結(jié)點(diǎn)是由數(shù)據(jù)元素的數(shù)據(jù)和下一個(gè)結(jié)點(diǎn)的地址組成，在java集合框架里面 ?LinkedList、HashMap（數(shù)組加鏈表）等等的底層都是用鏈表實(shí)現(xiàn)的。

2、下面是單鏈表的幾個(gè)特點(diǎn)：

數(shù)據(jù)元素在內(nèi)存中存放的地址是不連續(xù)的：?jiǎn)捂湵淼慕Y(jié)點(diǎn)里面還定義一個(gè)結(jié)點(diǎn)，它里面保存著下一個(gè)結(jié)點(diǎn)的內(nèi)存地址，在實(shí)例化對(duì)象的時(shí)候，jvm會(huì)開辟不同內(nèi)存空間，并且是不連續(xù)的。

添加效率高：添加一個(gè)元素時(shí)，先找到插入位置的前一個(gè)，只需要將1，2個(gè)元素的連接斷開，將插入結(jié)點(diǎn)的next指向第一個(gè)元素的next

（1），然后將第一個(gè)元素的next指向插入結(jié)點(diǎn)（2），

不用在挪動(dòng)后面元素。

刪除效率高：刪除一個(gè)元素時(shí)，先找到刪除位置，將前一個(gè)的next指向刪除位置的next，不用在挪動(dòng)后面元素。

查詢效率低：查詢的時(shí)候必須從頭開始，依次遍歷，而數(shù)組因?yàn)樗膬?nèi)存是連續(xù)的，可以直接通過(guò)索引查找。

3、下面通過(guò)代碼來(lái)實(shí)現(xiàn)單鏈表結(jié)構(gòu)：

package?com.tlinkedList;

/**
*?User:zhang
*?Date:2020/10/26
**/
public?class?TLinkedList<T>?{
??private?Node?head;//鏈表頭部
??private?int?size;//鏈表元素的個(gè)數(shù)
??public?TLinkedList(){
??????head=null;
??????size=0;
??}
//????將結(jié)點(diǎn)作為內(nèi)部類。也可以新建一個(gè)Node類，作為結(jié)點(diǎn)
??class?Node{
??????private?Node?next;//下一個(gè)結(jié)點(diǎn)
??????private?T?t;//結(jié)點(diǎn)的數(shù)據(jù)
??????public?Node(T?t){
??????????this.t=t;
??????}

??????public?T?getT()?{
??????????return?t;
??????}

??????public?void?setT(T?t)?{
??????????this.t?=?t;
??????}
??}
//????在鏈表頭部添加一個(gè)結(jié)點(diǎn)
??public?void?addFirst(T?t){
??????Node?node?=?new?Node(t);
??????node.next=head;
??????head=node;
??????size++;
??}
//????在鏈表中間添加一個(gè)結(jié)點(diǎn)
??public?void?addMid(T?t,int?index){
??????Node?node?=?new?Node(t);
??????Node?mid=head;
??????for?(int?i?=?0;?i?1;?i++)?{
??????????mid=mid.next;
??????}
??????node.next=mid.next;
??????mid.next=node;
??????size++;
??}
//????在鏈表尾部添加一個(gè)結(jié)點(diǎn)
??public?void?addLast(T?t){
??????Node?node?=?new?Node(t);
??????Node?last=head;
??????while?(last.next!=null){
??????????last=last.next;
??????}
??????last.next=node;
??????node.next=null;
??????size++;
??}
//????刪除鏈表的頭結(jié)點(diǎn)
??public?void?removeFirst(){
??????head=head.next;
??????size--;
??}
//????刪除鏈表的中間元素
??public?void?removeMid(int?index){
??????Node?mid=head;
??????if?(index==0){
??????????removeFirst();
??????????return;
??????}
??????int?j=0;
??????Node?qMid=head;
??????while?(j??????????qMid=mid;
??????????mid=mid.next;
??????????j++;
??????}
??????qMid.next=mid.next;
??????size--;
??}
//????刪除鏈表的尾結(jié)點(diǎn)
??public?void?removeLast(){
??????Node?mid=head;
??????Node?qMid=head;
??????while?(mid.next!=null){
???????????qMid=mid;
???????????mid=mid.next;
??????}
??????qMid.next=?null;
??????size--;
??}
//????獲取鏈表指定下標(biāo)的結(jié)點(diǎn)
??public?Node?get(int?index){
??????Node?mid=head;
??????if?(index==0){
??????????return?head;
??????}
??????int?j=0;
??????while?(j??????????mid=mid.next;
??????????j++;
??????}
??????return?mid;
??}
??public?static?void?main(String[]?args)?{
??????TLinkedList?linkedList?=?new?TLinkedList<>();
??????linkedList.addFirst("hello1");
??????linkedList.addFirst("hello2");
??????linkedList.addFirst("hello3");
??????for?(int?i?=?0;?i???????????System.out.println(linkedList.get(i).getT());
??????}
//????????linkedList.removeLast();
//????????linkedList.removeFirst();
//????????linkedList.addLast("hello4");
??????linkedList.addMid("hello",2);
??????System.out.println("--------------");
??????for?(int?i?=?0;?i???????????System.out.println(linkedList.get(i).getT());
??????}
??}
}

結(jié)果如下：

二、棧(Stack)

1、一提到棧我們腦海就會(huì)浮現(xiàn)四個(gè)字“先進(jìn)后出”，沒錯(cuò)，它就是棧的最大特點(diǎn)。

2、棧的應(yīng)用場(chǎng)景也非常多，比如將字符串反轉(zhuǎn)、jvm里面的棧區(qū)等等。

3、棧里面的主要操作有：

• push（入棧）：將一個(gè)數(shù)據(jù)元素從尾部插入
• pop（出棧）：將一個(gè)數(shù)據(jù)元素從尾部刪除
• peek（返回棧頂元素）：將棧頂元素的數(shù)據(jù)返回
  相當(dāng)于只有一個(gè)開口就是尾部，只能從尾進(jìn)，從尾出。

4、下面通過(guò)鏈表結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu)：

package?com.tStack;


/**
*?User:zhang
*?Date:2020/10/26
**/
public?class?Test_Stack<T>?{
??private?Node?head;//棧的頭結(jié)點(diǎn)
??private?int?size;//棧的元素個(gè)數(shù)
??class?Node{
??????private?Node?next;//下一個(gè)結(jié)點(diǎn)
??????private?T?t;//結(jié)點(diǎn)的數(shù)據(jù)
??????public?Node(T?t){
??????????this.t=t;
??????}

??????public?T?getT()?{
??????????return?t;
??????}

??????public?void?setT(T?t)?{
??????????this.t?=?t;
??????}
??}

??public?Test_Stack()?{
??????head=null;
??????size=0;
??}

??public?static?void?main(String[]?args)?{
??????Test_Stack?TStack?=?new?Test_Stack<>();
??????TStack.push("hello1");
??????TStack.push("hello2");
??????TStack.push("hello3");
??????for?(int?i?=?0;?i?3;?i++)?{
??????????System.out.println(TStack.pop());
??????}
??}
//????入棧
??public?void?push(T?t){
??????Node?node?=?new?Node(t);
??????if?(size==0){
??????????node.next=head;
??????????head=node;
??????????size++;
??????????return;
??????}
??????if?(size==1){
??????????head.next=node;
??????????node.next=null;
??????????size++;
??????????return;
??????}
??????Node?lastNode=head;
??????while?(lastNode.next!=null){
???????????lastNode=lastNode.next;
??????}
??????lastNode.next=node;
??????node.next=null;
??????size++;
??}
//????出棧
??public?T?pop(){
??????if?(size==0){
??????????System.out.println("棧內(nèi)無(wú)值");
??????????return?null;
??????}
??????if?(size==1){
??????????T?t?=?head.getT();
??????????head=null;
??????????size--;
??????????return?t;
??????}
??????Node?lastNode=head;
??????Node?qNode=head;
??????while?(lastNode.next!=null){
??????????qNode=lastNode;
??????????lastNode=lastNode.next;
??????}
??????T?t?=?lastNode.getT();
??????qNode.next=null;
??????size--;
??????return?t;
??}
//????獲取棧里面元素的個(gè)數(shù)
??public?int?getSize(){
??????return?size;
??}
//????返回棧頂元素
??public?T?peek(){
??????if?(size==0){
??????????System.out.println("棧內(nèi)無(wú)值");
??????????return?null;
??????}
??????if?(size==1){
??????????return?head.getT();
??????}
??????Node?lastNode=head;
??????while?(lastNode.next!=null){
??????????lastNode=lastNode.next;
??????}
??????return?lastNode.getT();
??}
}

結(jié)果：

三、隊(duì)列(Queue)

1、隊(duì)列的特點(diǎn)也用“先進(jìn)先出”四個(gè)字來(lái)概括。就是先進(jìn)去的元素先輸出出來(lái)。

2、我們常見的消息隊(duì)列就是隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)的。

3、隊(duì)列的常見操作如下：

• put（入隊(duì)）：將一個(gè)結(jié)點(diǎn)插入到尾部。
• pop（出隊(duì)）：將頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)作為頭，然后將原來(lái)的頭結(jié)點(diǎn)刪除。

4、通過(guò)鏈表結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列：

package?com.tQueue;

/**
?*?User:zhang
?*?Date:2020/10/26
?**/
public?class?TQueue<T>?{
????private?Node?front;//頭結(jié)點(diǎn)
????private?Node?tail;//尾結(jié)點(diǎn)
????private?int?size;//隊(duì)列中元素的個(gè)數(shù)
????class?Node?{
????????private?Node?next;//下一個(gè)結(jié)點(diǎn)
????????private?T?t;//結(jié)點(diǎn)的數(shù)據(jù)

????????public?Node(T?t)?{
????????????this.t?=?t;
????????}

????????public?T?getT()?{
????????????return?t;
????????}

????????public?void?setT(T?t)?{
????????????this.t?=?t;
????????}
????}
????public?int?getSize()?{
????????return?size;
????}

????public?void?setSize(int?size)?{
????????this.size?=?size;
????}

????public?TQueue()?{
????????front?=?tail?=?null;
????}

????//????入隊(duì)
????public?void?put(T?t)?{
????????Node?node?=?new?Node(t);
????????if?(size?==?0)?{
????????????front?=?tail?=?node;
????????????size++;
????????????return;
????????}
????????Node?lastNode?=?front;
????????while?(lastNode.next?!=?null)?{
????????????lastNode?=?lastNode.next;
????????}
????????lastNode.next?=?node;
????????tail?=?node;
????????size++;
????}

????//????出隊(duì)
????public?T?pop()?{
????????if?(size?==?0)?{
????????????System.out.println("隊(duì)列中無(wú)值");
????????????return?null;
????????}
????????T?t?=?front.getT();
????????front=front.next;
????????size--;
????????return?t;
????}

????public?static?void?main(String[]?args)?{
????????TQueue?tQueue?=?new?TQueue<>();
????????tQueue.put("Hello1");
????????tQueue.put("Hello2");
????????tQueue.put("Hello3");
????????for?(int?i?=?0;?i?3;?i++)?{
????????????System.out.println(tQueue.pop());
????????}
????}
}

結(jié)果：

文章有不足之處，歡迎大家留言指正，謝謝大家啦！