投稿
  1. 簡單一點首頁
  2. 編程

java雙向鏈表,java雙向鏈表反轉

小藍 • • 編程

本文目錄一覽：

在java中實現雙向鏈表的 clone() 方法

為什麼要自己寫雙向鏈表啊？

java中的 java.util.LinkedList 類就是一個已經封裝好的雙向鏈表。

他的clone()方法： 返回此 LinkedList 的淺表副本。（這些元素本身沒有複製。）

用JAVA語言，編寫一個鏈表類(雙向鏈表),實現插入,刪除,查找操作。新手，要俗易懂些，最好自己調適通過。急

定義接口：

//Deque.java

package dsa; //根據自己的程序位置不同

public interface Deque {

public int getSize();//返回隊列中元素數目

public boolean isEmpty();//判斷隊列是否為空

public Object first() throws ExceptionQueueEmpty;//取首元素（但不刪除）

public Object last() throws ExceptionQueueEmpty;//取末元素（但不刪除）

public void insertFirst(Object obj);//將新元素作為首元素插入

public void insertLast(Object obj);//將新元素作為末元素插入

public Object removeFirst() throws ExceptionQueueEmpty;//刪除首元素

public Object removeLast() throws ExceptionQueueEmpty;//刪除末元素

public void Traversal();//遍歷

}

雙向鏈表實現：

//Deque_DLNode.java

/*

* 基於雙向鏈表實現雙端隊列結構

*/

package dsa;

public class Deque_DLNode implements Deque {

protected DLNode header;//指向頭節點（哨兵）

protected DLNode trailer;//指向尾節點（哨兵）

protected int size;//隊列中元素的數目

//構造函數

public Deque_DLNode() {

header = new DLNode();

trailer = new DLNode();

header.setNext(trailer);

trailer.setPrev(header);

size = 0;

}

//返回隊列中元素數目

public int getSize()

{ return size; }

//判斷隊列是否為空

public boolean isEmpty()

{ return (0 == size) ? true : false; }

//取首元素（但不刪除）

public Object first() throws ExceptionQueueEmpty {

if (isEmpty())

throw new ExceptionQueueEmpty(“意外：雙端隊列為空”);

return header.getNext().getElem();

}

//取末元素（但不刪除）

public Object last() throws ExceptionQueueEmpty {

if (isEmpty())

throw new ExceptionQueueEmpty(“意外：雙端隊列為空”);

return trailer.getPrev().getElem();

}

//在隊列前端插入新節點

public void insertFirst(Object obj) {

DLNode second = header.getNext();

DLNode first = new DLNode(obj, header, second);

second.setPrev(first);

header.setNext(first);

size++;

}

//在隊列後端插入新節點

public void insertLast(Object obj) {

DLNode second = trailer.getPrev();

DLNode first = new DLNode(obj, second, trailer);

second.setNext(first);

trailer.setPrev(first);

size++;

}

//刪除首節點

public Object removeFirst() throws ExceptionQueueEmpty {

if (isEmpty())

throw new ExceptionQueueEmpty(“意外：雙端隊列為空”);

DLNode first = header.getNext();

DLNode second = first.getNext();

Object obj = first.getElem();

header.setNext(second);

second.setPrev(header);

size–;

return(obj);

}

//刪除末節點

public Object removeLast() throws ExceptionQueueEmpty {

if (isEmpty())

throw new ExceptionQueueEmpty(“意外：雙端隊列為空”);

DLNode first = trailer.getPrev();

DLNode second = first.getPrev();

Object obj = first.getElem();

trailer.setPrev(second);

second.setNext(trailer);

size–;

return(obj);

}

//遍歷

public void Traversal() {

DLNode p = header.getNext();

while (p != trailer) {

System.out.print(p.getElem()+” “);

p = p.getNext();

}

System.out.println();

}

}

用JAVA語言解決：編寫一個鏈表類(雙向鏈表),實現插入,刪除,查找操作

public class DoubleLinkedList

{

// 節點類Node

private static class Node

{

Object value;

Node prev = this;

Node next = this;

Node(Object v)

{

value = v;

}

public String toString()

{

return value.toString();

}

}

private Node head = new Node(null); // 頭節點

private int size; // 鏈表大小

// 以下是接口方法

public boolean addFirst(Object o)

{

addAfter(new Node(o), head);

return true;

}

public boolean addLast(Object o)

{

addBefore(new Node(o), head);

return true;

}

public boolean add(Object o)

{

return addLast(o);

}

public boolean add(int index, Object o)

{

addBefore(new Node(o), getNode(index));

return true;

}

public boolean remove(int index)

{

removeNode(getNode(index));

return true;

}

public boolean removeFirst()

{

removeNode(head.next);

return true;

}

public boolean removeLast()

{

removeNode(head.prev);

return true;

}

public Object get(int index)

{

return getNode(index).value;

}

public int size()

{

return size;

}

public String toString()

{

StringBuffer s = new StringBuffer(“[“);

Node node = head;

for (int i = 0; i size; i++)

{

node = node.next;

if (i 0)

s.append(“, “);

s.append(node.value);

}

s.append(“]”);

return s.toString();

}

private Node getNode(int index)

{

if (index 0 || index = size)

throw new IndexOutOfBoundsException();

Node node = head.next;

for (int i = 0; i index; i++)

node = node.next;

return node;

}

private void addBefore(Node newNode, Node node)

{

newNode.next = node;

newNode.prev = node.prev;

newNode.next.prev = newNode;

newNode.prev.next = newNode;

size++;

}

private void addAfter(Node newNode, Node node)

{

newNode.prev = node;

newNode.next = node.next;

newNode.next.prev = newNode;

newNode.prev.next = newNode;

size++;

}

private void removeNode(Node node)

{

node.prev.next = node.next;

node.next.prev = node.prev;

node.prev = null;

node.next = null;

size–;

}

}

//測試類：

public class Test

{

public static void main(String[] args)

{

DoubleLinkedList dll = new DoubleLinkedList();

//添加

dll.add(“張三”);

dll.add(“李四”);

dll.add(“王五”);

System.out.println(dll);

//添加到最前

dll.addFirst(“孫七”);

System.out.println(dll);

//添加到最後，同添加

dll.addLast(“趙六”);

System.out.println(dll);

//添加到指定位置

dll.add(4, “王祖賢”);

System.out.println(dll);

//移除最前的

dll.removeFirst();

System.out.println(dll);

//移除最後的

dll.removeLast();

System.out.println(dll);

//移除指定位置上的

dll.remove(2);

System.out.println(dll);

//返回指定位置上的元素

System.out.println(dll.get(1));

}

}

java中 雙向鏈表是什麼意思啊，是用來幹啥的啊，求大神解答？謝謝

採用雙向循環鏈表作為數據結構

1 新元素的下一個指向header

2 新元素的上一個指向header的上一個

3 新元素的上一個的下一個指向新元素

4 新元素的下一個的上一個指向新元素

一般LinkedList是採用雙向循環鏈表，無需擴容，添加元素添加到最後即可

在Java中如何實現雙向鏈表?

雙向鏈表：就是有雙向指針，即雙向的鏈域。\x0d\x0a鏈結點的結構：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a雙向鏈表不必是雙端鏈表(持有對最後一個鏈結點的引用)，雙端鏈表插入時是雙向的。\x0d\x0a有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。\x0d\x0a/**\x0d\x0a * 雙向鏈表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0a private Link head; //首結點\x0d\x0a private Link rear; //尾部指針\x0d\x0a public DoublyLinkedList() { }\x0d\x0a public T peekHead() {\x0d\x0a if (head != null) {\x0d\x0a return head.data;\x0d\x0a }\x0d\x0a return null;\x0d\x0a }\x0d\x0a public boolean isEmpty() {\x0d\x0a return head == null;\x0d\x0a }\x0d\x0a public void insertFirst(T data) {// 插入 到 鏈頭\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {//為空時，第1次插入的新結點為尾結點\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a head.previous = newLink; //舊頭結點的上結點等於新結點\x0d\x0a }\x0d\x0a newLink.next = head; //新結點的下結點舊頭結點\x0d\x0a head = newLink; //賦值後，頭結點的下結點是舊頭結點，上結點null\x0d\x0a }\x0d\x0a public void insertLast(T data) {//在鏈尾 插入\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {\x0d\x0a head = newLink;\x0d\x0a } else {\x0d\x0a rear.next = newLink;\x0d\x0a }\x0d\x0a newLink.previous = rear;\x0d\x0a rear = newLink; //賦值後，尾結點的上結點是舊尾結點，下結點null\x0d\x0a }\x0d\x0a public T deleteHead() {//刪除 鏈頭\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = head;\x0d\x0a head = head.next; //變更首結點，為下一結點\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a } else {\x0d\x0a rear = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T deleteRear() {//刪除 鏈尾\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = rear;\x0d\x0a rear = rear.previous; //變更尾結點，為上一結點\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a } else {\x0d\x0a head = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T find(T t) {//從頭到尾find\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link find = head;\x0d\x0a while (find != null) {\x0d\x0a if (!find.data.equals(t)) {\x0d\x0a find = find.next;\x0d\x0a } else {\x0d\x0a break;\x0d\x0a }\x0d\x0a }\x0d\x0a if (find == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a return find.data;\x0d\x0a }\x0d\x0a public T delete(T t) {\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(t)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a }\x0d\x0a if (current == head) {\x0d\x0a head = head.next;\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a }\x0d\x0a } else if (current == rear) {\x0d\x0a rear = rear.previous;\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a }\x0d\x0a } else {\x0d\x0a //中間的非兩端的結點，要移除current\x0d\x0a current.next.previous = current.previous;\x0d\x0a current.previous.next = current.next;\x0d\x0a }\x0d\x0a return current.data;\x0d\x0a }\x0d\x0a public boolean insertAfter(T key, T data) {//插入在key之後, key不存在return false\x0d\x0a if (isEmpty()) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(key)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a }\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (current == rear) {\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a newLink.next = current.next;\x0d\x0a current.next.previous = newLink;\x0d\x0a }\x0d\x0a current.next = newLink;\x0d\x0a newLink.previous = current;\x0d\x0a return true;\x0d\x0a }\x0d\x0a public void displayList4Head() {//從頭開始遍歷\x0d\x0a System.out.println(“List (first–last):”);\x0d\x0a Link current = head;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.next;\x0d\x0a }\x0d\x0a }\x0d\x0a public void displayList4Rear() {//從尾開始遍歷\x0d\x0a System.out.println(“List (last–first):”);\x0d\x0a Link current = rear;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.previous;\x0d\x0a }\x0d\x0a }\x0d\x0a\x0d\x0a class Link {//鏈結點\x0d\x0a T data; //數據域\x0d\x0a Link next; //後繼指針，結點 鏈域\x0d\x0a Link previous; //前驅指針，結點 鏈域\x0d\x0a Link(T data) {\x0d\x0a this.data = data;\x0d\x0a }\x0d\x0a void displayLink() {\x0d\x0a System.out.println(“the data is ” + data.toString());\x0d\x0a }\x0d\x0a }\x0d\x0a public static void main(String[] args) {\x0d\x0a DoublyLinkedList list = new DoublyLinkedList();\x0d\x0a list.insertLast(1);\x0d\x0a list.insertFirst(2);\x0d\x0a list.insertLast(3);\x0d\x0a list.insertFirst(4);\x0d\x0a list.insertLast(5);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteHead = list.deleteHead();\x0d\x0a System.out.println(“deleteHead:” + deleteHead);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteRear = list.deleteRear();\x0d\x0a System.out.println(“deleteRear:” + deleteRear);\x0d\x0a list.displayList4Rear();\x0d\x0a System.out.println(“find:” + list.find(6));\x0d\x0a System.out.println(“find:” + list.find(3));\x0d\x0a System.out.println(“delete find:” + list.delete(6));\x0d\x0a System.out.println(“delete find:” + list.delete(1));\x0d\x0a list.displayList4Head();\x0d\x0a System.out.println(“—-在指定key後插入—-“);\x0d\x0a list.insertAfter(2, 8);\x0d\x0a list.insertAfter(2, 9);\x0d\x0a list.insertAfter(9, 10);\x0d\x0a list.displayList4Head();\x0d\x0a }\x0d\x0a}

在Java中如何實現雙向鏈表

雙向鏈表：就是有雙向指針，即雙向的鏈域。

鏈結點的結構：

┌────┬────┬────────┐

│ data │ next │ previous │

└────┴────┴────────┘

雙向鏈表不必是雙端鏈表(持有對最後一個鏈結點的引用)，雙端鏈表插入時是雙向的。

有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。

/**

* 雙向鏈表

*/

public class DoublyLinkedListt {

private Linkt head; //首結點

private Linkt rear; //尾部指針

public DoublyLinkedList() { }

public T peekHead() {

if (head != null) {

return head.data;

}

return null;

}

public boolean isEmpty() {

return head == null;

}

public void insertFirst(T data) {// 插入 到 鏈頭

Linkt newLink = new Linkt(data);

if (isEmpty()) {//為空時，第1次插入的新結點為尾結點

rear = newLink;

} else {

head.previous = newLink; //舊頭結點的上結點等於新結點

}

newLink.next = head; //新結點的下結點舊頭結點

head = newLink; //賦值後，頭結點的下結點是舊頭結點，上結點null

}

public void insertLast(T data) {//在鏈尾 插入

Linkt newLink = new Linkt(data);

if (isEmpty()) {

head = newLink;

} else {

rear.next = newLink;

}

newLink.previous = rear;

rear = newLink; //賦值後，尾結點的上結點是舊尾結點，下結點null

}

public T deleteHead() {//刪除 鏈頭

if (isEmpty()) return null;

Linkt temp = head;

head = head.next; //變更首結點，為下一結點

if (head != null) {

head.previous = null;

} else {

rear = null;

}

return temp.data;

}

public T deleteRear() {//刪除 鏈尾

if (isEmpty()) return null;

Linkt temp = rear;

rear = rear.previous; //變更尾結點，為上一結點

if (rear != null) {

rear.next = null;

} else {

head = null;

}

return temp.data;

}

public T find(T t) {//從頭到尾find

if (isEmpty()) {

return null;

}

Linkt find = head;

while (find != null) {

if (!find.data.equals(t)) {

find = find.next;

} else {

break;

}

}

if (find == null) {

return null;

}

return find.data;

}

public T delete(T t) {

if (isEmpty()) {

return null;

}

Linkt current = head;

while (!current.data.equals(t)) {

current = current.next;

if (current == null) {

return null;

}

}

if (current == head) {

head = head.next;

if (head != null) {

head.previous = null;

}

} else if (current == rear) {

rear = rear.previous;

if (rear != null) {

rear.next = null;

}

} else {

//中間的非兩端的結點，要移除current

current.next.previous = current.previous;

current.previous.next = current.next;

}

return current.data;

}

public boolean insertAfter(T key, T data) {//插入在key之後, key不存在return false

if (isEmpty()) {

return false;

}

Linkt current = head;

while (!current.data.equals(key)) {

current = current.next;

if (current == null) {

return false;

}

}

Linkt newLink = new Linkt(data);

if (current == rear) {

rear = newLink;

} else {

newLink.next = current.next;

current.next.previous = newLink;

}

current.next = newLink;

newLink.previous = current;

return true;

}

public void displayList4Head() {//從頭開始遍歷

System.out.println(“List (first–last):”);

Linkt current = head;

while (current != null) {

current.displayLink();

current = current.next;

}

}

public void displayList4Rear() {//從尾開始遍歷

System.out.println(“List (last–first):”);

Linkt current = rear;

while (current != null) {

current.displayLink();

current = current.previous;

}

}

class Linkt {//鏈結點

T data; //數據域

Linkt next; //後繼指針，結點 鏈域

Linkt previous; //前驅指針，結點 鏈域

Link(T data) {

this.data = data;

}

void displayLink() {

System.out.println(“the data is ” + data.toString());

}

}

public static void main(String[] args) {

DoublyLinkedListinteger list = new DoublyLinkedListinteger();

list.insertLast(1);

list.insertFirst(2);

list.insertLast(3);

list.insertFirst(4);

list.insertLast(5);

list.displayList4Head();

Integer deleteHead = list.deleteHead();

System.out.println(“deleteHead:” + deleteHead);

list.displayList4Head();

Integer deleteRear = list.deleteRear();

System.out.println(“deleteRear:” + deleteRear);

list.displayList4Rear();

System.out.println(“find:” + list.find(6));

System.out.println(“find:” + list.find(3));

System.out.println(“delete find:” + list.delete(6));

System.out.println(“delete find:” + list.delete(1));

list.displayList4Head();

System.out.println(“—-在指定key後插入—-“);

list.insertAfter(2, 8);

list.insertAfter(2, 9);

list.insertAfter(9, 10);

list.displayList4Head();

}

}

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/290787.html

贊 (0)
打賞 微信掃一掃 微信掃一掃 支付寶掃一掃 支付寶掃一掃
小藍的頭像小藍
0 0
上一篇 2024-12-24 13:13
下一篇 2024-12-24 13:13

相關推薦

  • Java JsonPath 效率優化指南

    本篇文章將深入探討Java JsonPath的效率問題，並提供一些優化方案。 一、JsonPath 簡介 JsonPath是一個可用於從JSON數據中獲取信息的庫。它提供了一種DS…

    IGTLV的頭像 IGTLV
    編程 2025-04-29

  • java client.getacsresponse 編譯報錯解決方法

    java client.getacsresponse 編譯報錯是Java編程過程中常見的錯誤，常見的原因是代碼的語法錯誤、類庫依賴問題和編譯環境的配置問題。下面將從多個方面進行分析…

    UBWYH的頭像 UBWYH
    編程 2025-04-29

  • Java騰訊雲音視頻對接

    本文旨在從多個方面詳細闡述Java騰訊雲音視頻對接，提供完整的代碼示例。 一、騰訊雲音視頻介紹 騰訊雲音視頻服務（Cloud Tencent Real-Time Communica…

    YXDEN的頭像 YXDEN
    編程 2025-04-29

  • Java Bean加載過程

    Java Bean加載過程涉及到類加載器、反射機制和Java虛擬機的執行過程。在本文中，將從這三個方面詳細闡述Java Bean加載的過程。 一、類加載器 類加載器是Java虛擬機…

    SUCQN的頭像 SUCQN
    編程 2025-04-29

  • Java Milvus SearchParam withoutFields用法介紹

    本文將詳細介紹Java Milvus SearchParam withoutFields的相關知識和用法。 一、什麼是Java Milvus SearchParam without…

    IQUKH的頭像 IQUKH
    編程 2025-04-29

  • 利用Python實現兩個鏈表合併為一個有序鏈表

    對於開發工程師來說，實現兩個鏈表合併為一個有序鏈表是必須掌握的技能之一。Python語言在鏈表處理上非常便利，本文將從多個方面詳細闡述如何利用Python實現兩個鏈表合併為一個有序…

    GWLMT的頭像 GWLMT
    編程 2025-04-29

  • Java 8中某一周的周一

    Java 8是Java語言中的一個版本，於2014年3月18日發佈。本文將從多個方面對Java 8中某一周的周一進行詳細的闡述。 一、數組處理 Java 8新特性之一是Stream…

    BYEUI的頭像 BYEUI
    編程 2025-04-29

  • Java判斷字符串是否存在多個

    本文將從以下幾個方面詳細闡述如何使用Java判斷一個字符串中是否存在多個指定字符： 一、字符串遍歷 字符串是Java編程中非常重要的一種數據類型。要判斷字符串中是否存在多個指定字符…

    KJBQQ的頭像 KJBQQ
    編程 2025-04-29

  • VSCode為什麼無法運行Java

    解答：VSCode無法運行Java是因為默認情況下，VSCode並沒有集成Java運行環境，需要手動添加Java運行環境或安裝相關插件才能實現Java代碼的編寫、調試和運行。 一、…

    GSABN的頭像 GSABN
    編程 2025-04-29

  • Java任務下發回滾系統的設計與實現

    本文將介紹一個Java任務下發回滾系統的設計與實現。該系統可以用於執行複雜的任務，包括可回滾的任務，及時恢復任務失敗前的狀態。系統使用Java語言進行開發，可以支持多種類型的任務。…

    BFFRU的頭像 BFFRU
    編程 2025-04-29

發表回復

登錄後才能評論