快捷導(dǎo)航

Java實(shí)現(xiàn)雙端鏈表LinkedList

更新時(shí)間：2022年07月14日 09:41:38 作者：一起努力啊啊啊啊

本文主要介紹了Java實(shí)現(xiàn)雙端鏈表LinkedList，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

一、LinkedList 介紹

1??LinkedList 是 Java 集合框架中一個(gè)重要的實(shí)現(xiàn)，其底層采用的雙向鏈表結(jié)構(gòu)，沒(méi)有初始化大小，就是一直在前面或者后面新增就好。由于基于鏈表實(shí)現(xiàn)，存儲(chǔ)元素過(guò)程中，無(wú)需像ArrayList那樣進(jìn)行擴(kuò)容。
2??LinkedList 存儲(chǔ)元素的節(jié)點(diǎn)需要額外的空間存儲(chǔ)前驅(qū)和后繼的引用。
3??LinkedList 在鏈表頭部和尾部插入效率比較高，但在指定位置進(jìn)行插入時(shí)，效率一般。原因是，在指定位置插入需要定位到該位置處的節(jié)點(diǎn)，此操作的時(shí)間復(fù)雜度為 O(N)。
4??和 ArrayList 一樣，LinkedList 也支持空值和重復(fù)值。LinkedList 也是非線(xiàn)程安全的集合類(lèi)。
5??由于 LinkedList 實(shí)現(xiàn)了 List 和 Deque 兩個(gè)接口，所以 LinkedList 方法分兩種，一種是 List 接口的方法，第二種是 Deque 接口的方法。
6??由于 LinkedList 是一個(gè)實(shí)現(xiàn)了 Deque 的雙端隊(duì)列，所以 LinkedList 既可以當(dāng)做Queue，又可以當(dāng)做 Stack。在將 LinkedList 當(dāng)做 Stack 時(shí)，使用 pop()、push()、peek() 需要注意的是 LinkedList 內(nèi)部是將鏈表頭部當(dāng)做棧頂，鏈表尾部當(dāng)做棧底。
7??隨機(jī)訪(fǎng)問(wèn)慢、插入刪除速度快。

二、LinkedList 使用

import java.util.Iterator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;


public class LinkedlistDemo {

? ? public static void main(String[] args) {
? ? ? ? linkedShow();
? ? ? ? System.out.println(">----------一&&&二----------<");
? ? ? ? linkedDeque();
? ? ? ? System.out.println(">----------二&&&三----------<");
? ? ? ? linkedListPop();
? ? }

? ? public static void linkedShow() {
? ? ? ? // 創(chuàng)建一個(gè)隊(duì)列
? ? ? ? Queue<Integer> queue = new LinkedList<>();
? ? ? ? //添加元素
? ? ? ? queue.add(1);
? ? ? ? queue.offer(22);
? ? ? ? for (Integer integer : queue) {
? ? ? ? ? ? System.out.println("queue的add()和offer()驗(yàn)證：" + integer);
? ? ? ? }

? ? ? ? // 獲取但不移除此隊(duì)列的頭
? ? ? ? Integer a = queue.peek();
? ? ? ? // 輸出獲取的元素并打印出元素的長(zhǎng)度，驗(yàn)證一下長(zhǎng)度看看是否有變化
? ? ? ? System.out.println("queue.peek()：" + a + "，后長(zhǎng)度為：" + queue.size());

? ? ? ? // 獲取并移除此隊(duì)列的頭
? ? ? ? Integer bInteger = queue.poll();
? ? ? ? // 輸出獲取的元素并打印出元素的長(zhǎng)度，驗(yàn)證一下長(zhǎng)度看看是否有變化
? ? ? ? System.out.println("queue.poll()：" + bInteger + "，后長(zhǎng)度為：" + queue.size());

? ? }

? ? public static void linkedDeque() {
? ? ? ? Deque<Integer> deque = new LinkedList<>();
? ? ? ? // 添加元素
? ? ? ? deque.add(3);
? ? ? ? // 在第一個(gè)位置添加元素
? ? ? ? deque.offerFirst(5);
? ? ? ? // 在最后一個(gè)位置添加元素
? ? ? ? deque.offerLast(7);
? ? ? ? for (Integer integer : deque) {
? ? ? ? ? ? System.out.println("deque新增驗(yàn)證：" + integer);
? ? ? ? }
? ? ? ? // 取出不移除元素
? ? ? ? Integer kInteger = deque.peekFirst();
? ? ? ? Integer mInteger = deque.peekLast();
? ? ? ? System.out.println("deque.peek()：" + kInteger + ">>>>" + mInteger + "，后長(zhǎng)度為：" + deque.size());
? ? ? ? // 取出并移除元素方法
? ? ? ? Integer kInteger2 = deque.pollFirst();
? ? ? ? Integer mInteger2 = deque.pollLast();
? ? ? ? System.out.println("deque.poll()：" + kInteger2 + ">>>>" + mInteger2 + "，后長(zhǎng)度為：" + deque.size());
? ? }

? ? public static void linkedListPop() {
? ? ? ? // 創(chuàng)建一個(gè)linkedlist集合
? ? ? ? LinkedList<Integer> linkedList = new LinkedList<>();
? ? ? ? // 添加元素
? ? ? ? linkedList.push(9);
? ? ? ? linkedList.push(7);
? ? ? ? linkedList.push(5);
? ? ? ? linkedList.push(3);
? ? ? ? linkedList.push(1);
? ? ? ? for (Integer integer : linkedList) {
? ? ? ? ? ? System.out.println("linkedList.push()：" + integer);
? ? ? ? }

? ? ? ? // 使用迭代器進(jìn)行正向輸出
? ? ? ? Iterator<Integer> inIterator = linkedList.iterator();
? ? ? ? while (inIterator.hasNext()) {
? ? ? ? ? ? Integer integer = inIterator.next();
? ? ? ? ? ? System.out.println(integer);
? ? ? ? }
? ? ? ? System.out.println("-------分割線(xiàn)-------");
? ? ? ? // 使用迭代器反向輸出結(jié)果
? ? ? ? Iterator<Integer> inIterator1 = linkedList.descendingIterator();
? ? ? ? while (inIterator1.hasNext()) {
? ? ? ? ? ? Integer integer = inIterator1.next();
? ? ? ? ? ? System.out.println(integer);
? ? ? ? }
? ? ? ? System.out.println("-------分割線(xiàn)-------");
? ? ? ? // 使用for循環(huán)進(jìn)行輸出元素并移除
? ? ? ? for (int i = 0; i <= 4; i++) {
? ? ? ? ? ? Integer result = linkedList.pop();
? ? ? ? ? ? System.out.println("linkedList.pop()：" + result + ">------<" + "，后長(zhǎng)度為：" + linkedList.size());
? ? ? ? }
? ? }
}

輸出如下：

queue的add()和offer()驗(yàn)證：1
queue的add()和offer()驗(yàn)證：22
queue.peek()：1，后長(zhǎng)度為：2
queue.poll()：1，后長(zhǎng)度為：1
>----------一&&&二----------<
deque新增驗(yàn)證：5
deque新增驗(yàn)證：3
deque新增驗(yàn)證：7
deque.peek()：5>>>>7，后長(zhǎng)度為：3
deque.poll()：5>>>>7，后長(zhǎng)度為：1
>----------二&&&三----------<
linkedList.push()：1
linkedList.push()：3
linkedList.push()：5
linkedList.push()：7
linkedList.push()：9
1
3
5
7
9
-------分割線(xiàn)-------
9
7
5
3
1
-------分割線(xiàn)-------
linkedList.pop()：1>------<，后長(zhǎng)度為：4
linkedList.pop()：3>------<，后長(zhǎng)度為：3
linkedList.pop()：5>------<，后長(zhǎng)度為：2
linkedList.pop()：7>------<，后長(zhǎng)度為：1
linkedList.pop()：9>------<，后長(zhǎng)度為：0

Process finished with exit code 0