鏈表java,鏈表java存儲

本文目錄一覽：

1、在Java中如何實現雙向鏈表?
2、Java語言沒有指針，怎樣實現鏈表?
3、java基本鏈表
4、java怎麼用鏈表實現

在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語言沒有指針，怎樣實現鏈表?

Java語言中的對象引用實際上是一個指針（這裡的指針均為概念上的意義，而非語言提供的數據類型），所以我們可以編寫這樣的類來實現鏈表中的結點。

private static class EntryE {

E element; // 當前存儲元素

EntryE next; // 下一個元素節點

EntryE previous; // 上一個元素節點

Entry(E element, EntryE next, EntryE previous) {

this.element = element;

this.next = next;

this.previous = previous;

}

將數據域定義成Object類是因為Object類是廣義超類，任何類對象都可以給其賦值，增加了代碼的通用性。為了使鏈表可以被訪問還需要定義一個表頭，表頭必須包含指向第一個結點的指針和指向當前結點的指針。為了便於在鏈表尾部增加結點，還可以增加一指向鏈表尾部的指針，另外還可以用一個域來表示鏈表的大小，當調用者想得到鏈表的大小時，不必遍歷整個鏈表。

鏈表的數據結構我們可以用類List來實現鏈表結構，用變量Head、Tail、Length、Pointer來實現表頭。

存儲當前結點的指針時有一定的技巧，Pointer並非存儲指向當前結點的指針，而是存儲指向它的前趨結點的指針,當其值為null時表示當前結點是第一個結點，因為當刪除當前結點後仍需保證剩下的結點構成鏈表，如果Pointer指向當前結點，則會給操作帶來很大困難。如何得到當前結點呢？我們定義了一個方法cursor(),返回值是指向當前結點的指針。類List還定義了一些方法來實現對鏈表的基本操作，通過運用這些基本操作我們可以對鏈表進行各種操作。

例如reset()方法使第一個結點成為當前結點。insert(Object d)方法在當前結點前插入一個結點，並使其成為當前結點。remove()方法刪除當前結點同時返回其內容，並使其後繼結點成為當前結點，如果刪除的是最後一個結點，則第一個結點變為當前結點。

java基本鏈表

傳進去的是new Node(“車廂A”)的引用

獲取當前節點的下一個節點， Node(“車頭！”) 的下一個節點是Node(“車廂A”)，Node(“車廂A”)的下一個節點是Node(“車廂B”)

java怎麼用鏈表實現

在數據結構中經常看見的一個基本概念-鏈表。

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

在Java中，對於鏈表的實現都是基於引用數據類型操作的。實現大致如下：

定義節點類Node，節點的概念很重要，一個鏈表是由各各節點連接在一起組成的。在節點類Node中定義節點內容及指向下一節點的引用，再增加一個添加節點的方法即可完成鏈表實現。

鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。在執行效率上，相比數組而言，鏈表插入快查找慢，開發中得根據實際業務使用。

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