一、單鏈表

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

2、下面是單鏈表的幾個特點：

數(shù)據(jù)元素在內(nèi)存中存放的地址是不連續(xù)的：單鏈表的結(jié)點里面還定義一個結(jié)點，它里面保存著下一個結(jié)點的內(nèi)存地址，在實例化對象的時候，jvm會開辟不同內(nèi)存空間，并且是不連續(xù)的。

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

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

不用在挪動后面元素。

刪除效率高：刪除一個元素時，先找到刪除位置，將前一個的next指向刪除位置的next，不用在挪動后面元素。

查詢效率低：查詢的時候必須從頭開始，依次遍歷，而數(shù)組因為它的內(nèi)存是連續(xù)的，可以直接通過索引查找。

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

package?com.tlinkedList;

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

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

??????public?void?setT(T?t)?{
??????????this.t?=?t;
??????}
??}
//????在鏈表頭部添加一個結(jié)點
??public?void?addFirst(T?t){
??????Node?node?=?new?Node(t);
??????node.next=head;
??????head=node;
??????size++;
??}
//????在鏈表中間添加一個結(jié)點
??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++;
??}
//????在鏈表尾部添加一個結(jié)點
??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é)點
??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é)點
??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é)點
??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、一提到棧我們腦海就會浮現(xiàn)四個字“先進后出”，沒錯，它就是棧的最大特點。

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

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

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

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

package?com.tStack;


/**
*?User:zhang
*?Date:2020/10/26
**/
public?class?Test_Stack<T>?{
??private?Node?head;//棧的頭結(jié)點
??private?int?size;//棧的元素個數(shù)
??class?Node{
??????private?Node?next;//下一個結(jié)點
??????private?T?t;//結(jié)點的數(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)無值");
??????????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;
??}
//????獲取棧里面元素的個數(shù)
??public?int?getSize(){
??????return?size;
??}
//????返回棧頂元素
??public?T?peek(){
??????if?(size==0){
??????????System.out.println("棧內(nèi)無值");
??????????return?null;
??????}
??????if?(size==1){
??????????return?head.getT();
??????}
??????Node?lastNode=head;
??????while?(lastNode.next!=null){
??????????lastNode=lastNode.next;
??????}
??????return?lastNode.getT();
??}
}

結(jié)果：

三、隊列(Queue)

1、隊列的特點也用“先進先出”四個字來概括。就是先進去的元素先輸出出來。

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

3、隊列的常見操作如下：

• put（入隊）：將一個結(jié)點插入到尾部。
• pop（出隊）：將頭結(jié)點的下一個結(jié)點作為頭，然后將原來的頭結(jié)點刪除。

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

package?com.tQueue;

/**
?*?User:zhang
?*?Date:2020/10/26
?**/
public?class?TQueue<T>?{
????private?Node?front;//頭結(jié)點
????private?Node?tail;//尾結(jié)點
????private?int?size;//隊列中元素的個數(shù)
????class?Node?{
????????private?Node?next;//下一個結(jié)點
????????private?T?t;//結(jié)點的數(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;
????}

????//????入隊
????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++;
????}

????//????出隊
????public?T?pop()?{
????????if?(size?==?0)?{
????????????System.out.println("隊列中無值");
????????????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é)果：

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