Java實現(xiàn)單鏈表、棧、隊列三種數(shù)據(jù)結(jié)構(gòu)
點擊上方 好好學(xué)java ，選擇 星標(biāo) 公眾號
重磅資訊，干貨，第一時間送達(dá)
今日推薦：推薦 19 個 github 超牛逼項目！
個人原創(chuàng)100W +訪問量博客：點擊前往，查看更多
作者：遠(yuǎn)航
cnblogs.com/yang-guang-zhang/p/13884023.html
一、單鏈表
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 < index - 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<index){
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<index){
mid=mid.next;
j++;
}
return mid;
}
public static void main(String[] args) {
TLinkedList<String> linkedList = new TLinkedList<>();
linkedList.addFirst("hello1");
linkedList.addFirst("hello2");
linkedList.addFirst("hello3");
for (int i = 0; i < linkedList.size; 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 < linkedList.size; i++) {
System.out.println(linkedList.get(i).getT());
}
}
}
結(jié)果如下：
二、棧(Stack)
1、一提到棧我們腦海就會浮現(xiàn)四個字“先進(jìn)后出”，沒錯，它就是棧的最大特點。
2、棧的應(yīng)用場景也非常多，比如將字符串反轉(zhuǎn)、jvm里面的棧區(qū)等等。
3、棧里面的主要操作有：
push（入棧）：將一個數(shù)據(jù)元素從尾部插入 pop（出棧）：將一個數(shù)據(jù)元素從尾部刪除 peek（返回棧頂元素）：將棧頂元素的數(shù)據(jù)返回
相當(dāng)于只有一個開口就是尾部，只能從尾進(jìn)，從尾出。
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<String> 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、隊列的特點也用“先進(jìn)先出”四個字來概括。就是先進(jìn)去的元素先輸出出來。
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<String> 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é)果：
文章有不足之處，歡迎大家留言指正，謝謝大家啦！
推薦文章
更多項目源碼
評論
圖片
表情