java鏈表雙向?qū)崿F(xiàn)代碼 雙向循環(huán)鏈表java
在java中實(shí)現(xiàn)雙向鏈表的 clone() 方法
為什么要自己寫雙向鏈表啊？
創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、銀海網(wǎng)絡(luò)推廣、重慶小程序開發(fā)、銀海網(wǎng)絡(luò)營銷、銀海企業(yè)策劃、銀海品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供銀海建站搭建服務(wù)，24小時(shí)服務(wù)熱線：028-86922220，官方網(wǎng)址：jinyejixie.com
java中的 java.util.LinkedList 類就是一個(gè)已經(jīng)封裝好的雙向鏈表。
他的clone()方法： 返回此 LinkedList 的淺表副本。（這些元素本身沒有復(fù)制。）
在Java中如何實(shí)現(xiàn)雙向鏈表
雙向鏈表：就是有雙向指針，即雙向的鏈域。
鏈結(jié)點(diǎn)的結(jié)構(gòu)：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
雙向鏈表不必是雙端鏈表(持有對最后一個(gè)鏈結(jié)點(diǎn)的引用)，雙端鏈表插入時(shí)是雙向的。
有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時(shí)也是雙向的。
/**
* 雙向鏈表
*/
public class DoublyLinkedListt {
private Linkt head; //首結(jié)點(diǎn)
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()) {//為空時(shí)，第1次插入的新結(jié)點(diǎn)為尾結(jié)點(diǎn)
rear = newLink;
} else {
head.previous = newLink; //舊頭結(jié)點(diǎn)的上結(jié)點(diǎn)等于新結(jié)點(diǎn)
}
newLink.next = head; //新結(jié)點(diǎn)的下結(jié)點(diǎn)舊頭結(jié)點(diǎn)
head = newLink; //賦值后，頭結(jié)點(diǎn)的下結(jié)點(diǎn)是舊頭結(jié)點(diǎn)，上結(jié)點(diǎn)null
}
public void insertLast(T data) {//在鏈尾 插入
Linkt newLink = new Linkt(data);
if (isEmpty()) {
head = newLink;
} else {
rear.next = newLink;
}
newLink.previous = rear;
rear = newLink; //賦值后，尾結(jié)點(diǎn)的上結(jié)點(diǎn)是舊尾結(jié)點(diǎn)，下結(jié)點(diǎn)null
}
public T deleteHead() {//刪除 鏈頭
if (isEmpty()) return null;
Linkt temp = head;
head = head.next; //變更首結(jié)點(diǎn)，為下一結(jié)點(diǎn)
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; //變更尾結(jié)點(diǎn)，為上一結(jié)點(diǎn)
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 {
//中間的非兩端的結(jié)點(diǎn)，要移除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 {//鏈結(jié)點(diǎn)
T data; //數(shù)據(jù)域
Linkt next; //后繼指針，結(jié)點(diǎn) 鏈域
Linkt previous; //前驅(qū)指針，結(jié)點(diǎn) 鏈域
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();
}
}
用JAVA語言，編寫一個(gè)鏈表類(雙向鏈表),實(shí)現(xiàn)插入,刪除,查找操作。新手，要俗易懂些，最好自己調(diào)適通過。急
定義接口：
//Deque.java
package dsa; //根據(jù)自己的程序位置不同
public interface Deque {
public int getSize();//返回隊(duì)列中元素?cái)?shù)目
public boolean isEmpty();//判斷隊(duì)列是否為空
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();//遍歷
}
雙向鏈表實(shí)現(xiàn)：
//Deque_DLNode.java
/*
* 基于雙向鏈表實(shí)現(xiàn)雙端隊(duì)列結(jié)構(gòu)
*/
package dsa;
public class Deque_DLNode implements Deque {
protected DLNode header;//指向頭節(jié)點(diǎn)（哨兵）
protected DLNode trailer;//指向尾節(jié)點(diǎn)（哨兵）
protected int size;//隊(duì)列中元素的數(shù)目
//構(gòu)造函數(shù)
public Deque_DLNode() {
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer);
trailer.setPrev(header);
size = 0;
}
//返回隊(duì)列中元素?cái)?shù)目
public int getSize()
{ return size; }
//判斷隊(duì)列是否為空
public boolean isEmpty()
{ return (0 == size) ? true : false; }
//取首元素（但不刪除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
return header.getNext().getElem();
}
//取末元素（但不刪除）
public Object last() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
return trailer.getPrev().getElem();
}
//在隊(duì)列前端插入新節(jié)點(diǎn)
public void insertFirst(Object obj) {
DLNode second = header.getNext();
DLNode first = new DLNode(obj, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
//在隊(duì)列后端插入新節(jié)點(diǎn)
public void insertLast(Object obj) {
DLNode second = trailer.getPrev();
DLNode first = new DLNode(obj, second, trailer);
second.setNext(first);
trailer.setPrev(first);
size++;
}
//刪除首節(jié)點(diǎn)
public Object removeFirst() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
DLNode first = header.getNext();
DLNode second = first.getNext();
Object obj = first.getElem();
header.setNext(second);
second.setPrev(header);
size--;
return(obj);
}
//刪除末節(jié)點(diǎn)
public Object removeLast() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
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語言解決：編寫一個(gè)鏈表類(雙向鏈表),實(shí)現(xiàn)插入,刪除,查找操作
public class DoubleLinkedList
{
// 節(jié)點(diǎn)類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); // 頭節(jié)點(diǎn)
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鏈表雙向?qū)崿F(xiàn)代碼 雙向循環(huán)鏈表java
標(biāo)題鏈接：http://jinyejixie.com/article48/hehehp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站策劃、、商城網(wǎng)站、動(dòng)態(tài)網(wǎng)站
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
