Java實現單鏈表、棧、隊列三種數據結構
作者：佚名
本文介紹了單鏈表、棧、隊列三種數據結構。一起來看看吧。
一、單鏈表
1、在我們數據結構中，單鏈表非常重要。它里面的數據元素是以結點為單位，每個結點是由數據元素的數據和下一個結點的地址組成，在java集合框架里面 LinkedList、HashMap（數組加鏈表）等等的底層都是用鏈表實現的。
2、下面是單鏈表的幾個特點：
數據元素在內存中存放的地址是不連續的：單鏈表的結點里面還定義一個結點，它里面保存著下一個結點的內存地址，在實例化對象的時候，jvm會開辟不同內存空間，并且是不連續的。
添加效率高：添加一個元素時，先找到插入位置的前一個，只需要將1，2個元素的連接斷開，將插入結點的next指向第一個元素的next
（1），然后將第一個元素的next指向插入結點（2），
不用在挪動后面元素。
刪除效率高：刪除一個元素時，先找到刪除位置，將前一個的next指向刪除位置的next，不用在挪動后面元素。
查詢效率低：查詢的時候必須從頭開始，依次遍歷，而數組因為它的內存是連續的，可以直接通過索引查找。
3、下面通過代碼來實現單鏈表結構：
- package com.tlinkedList;
- /**
- * User:zhang
- * Date:2020/10/26
- **/
- public class TLinkedList<T> {
- private Node head;//鏈表頭部
- private int size;//鏈表元素的個數
- public TLinkedList(){
- head=null;
- size=0;
- }
- // 將結點作為內部類。也可以新建一個Node類，作為結點
- class Node{
- private Node next;//下一個結點
- private T t;//結點的數據
- public Node(T t){
- tthis.t=t;
- }
- public T getT() {
- return t;
- }
- public void setT(T t) {
- tthis.t = t;
- }
- }
- // 在鏈表頭部添加一個結點
- public void addFirst(T t){
- Node node = new Node(t);
- node.next=head;
- head=node;
- size++;
- }
- // 在鏈表中間添加一個結點
- public void addMid(T t,int index){
- Node node = new Node(t);
- Node mid=head;
- for (int i = 0; i < index - 1; i++) {
- midmid=mid.next;
- }
- node.next=mid.next;
- mid.next=node;
- size++;
- }
- // 在鏈表尾部添加一個結點
- public void addLast(T t){
- Node node = new Node(t);
- Node last=head;
- while (last.next!=null){
- lastlast=last.next;
- }
- last.next=node;
- node.next=null;
- size++;
- }
- // 刪除鏈表的頭結點
- public void removeFirst(){
- headhead=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;
- midmid=mid.next;
- j++;
- }
- qMid.next=mid.next;
- size--;
- }
- // 刪除鏈表的尾結點
- public void removeLast(){
- Node mid=head;
- Node qMid=head;
- while (mid.next!=null){
- qMid=mid;
- midmid=mid.next;
- }
- qMid.next= null;
- size--;
- }
- // 獲取鏈表指定下標的結點
- public Node get(int index){
- Node mid=head;
- if (index==0){
- return head;
- }
- int j=0;
- while (j<index){
- midmid=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());
- }
- }
- }
結果如下：
二、棧(Stack)
1、一提到棧我們腦海就會浮現四個字“先進后出”，沒錯，它就是棧的最大特點。
2、棧的應用場景也非常多，比如將字符串反轉、jvm里面的棧區等等。
3、棧里面的主要操作有：
- push（入棧）：將一個數據元素從尾部插入
- pop（出棧）：將一個數據元素從尾部刪除
- peek（返回棧頂元素）：將棧頂元素的數據返回
相當于只有一個開口就是尾部，只能從尾進，從尾出。
4、下面通過鏈表結構實現棧結構：
- package com.tStack;
- /**
- * User:zhang
- * Date:2020/10/26
- **/
- public class Test_Stack<T> {
- private Node head;//棧的頭結點
- private int size;//棧的元素個數
- class Node{
- private Node next;//下一個結點
- private T t;//結點的數據
- public Node(T t){
- tthis.t=t;
- }
- public T getT() {
- return t;
- }
- public void setT(T t) {
- tthis.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){
- lastNodelastNode=lastNode.next;
- }
- lastNode.next=node;
- node.next=null;
- size++;
- }
- // 出棧
- public T pop(){
- if (size==0){
- System.out.println("棧內無值");
- 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;
- lastNodelastNode=lastNode.next;
- }
- T t = lastNode.getT();
- qNode.next=null;
- size--;
- return t;
- }
- // 獲取棧里面元素的個數
- public int getSize(){
- return size;
- }
- // 返回棧頂元素
- public T peek(){
- if (size==0){
- System.out.println("棧內無值");
- return null;
- }
- if (size==1){
- return head.getT();
- }
- Node lastNode=head;
- while (lastNode.next!=null){
- lastNodelastNode=lastNode.next;
- }
- return lastNode.getT();
- }
- }
結果：
三、隊列(Queue)
1、隊列的特點也用“先進先出”四個字來概括。就是先進去的元素先輸出出來。
2、我們常見的消息隊列就是隊列結構實現的。
3、隊列的常見操作如下：
- put（入隊）：將一個結點插入到尾部。
- pop（出隊）：將頭結點的下一個結點作為頭，然后將原來的頭結點刪除。
4、通過鏈表結構實現隊列：
- package com.tQueue;
- /**
- * User:zhang
- * Date:2020/10/26
- **/
- public class TQueue<T> {
- private Node front;//頭結點
- private Node tail;//尾結點
- private int size;//隊列中元素的個數
- class Node {
- private Node next;//下一個結點
- private T t;//結點的數據
- public Node(T t) {
- tthis.t = t;
- }
- public T getT() {
- return t;
- }
- public void setT(T t) {
- tthis.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) {
- lastNodelastNode = lastNode.next;
- }
- lastNode.next = node;
- tail = node;
- size++;
- }
- // 出隊
- public T pop() {
- if (size == 0) {
- System.out.println("隊列中無值");
- return null;
- }
- T t = front.getT();
- frontfront=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());
- }
- }
- }
結果：
責任編輯：龐桂玉
來源：
Java知音
