java實現雙向鏈表的增刪功能（Java 雙向鏈表）

本文目錄一覽：

• 1、用JAVA語言解決：編寫一個鏈表類(雙向鏈表),實現插入,刪除,查找操作
• 2、用JAVA語言，編寫一個鏈表類(雙向鏈表),實現插入,刪除,查找操作。新手，要俗易懂些，最好自己調適通過。急
• 3、在Java中如何實現雙向鏈表

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

定義介面：

//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中如何實現雙向鏈表

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

鏈結點的結構：

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

│ 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();

}

}