java链表双向实现代码 双向循环链表java

在java中实现双向链表的 clone() 方法

为什么要自己写双向链表啊？

java中的 java.util.LinkedList 类就是一个已经封装好的双向链表。

他的clone()方法： 返回此 LinkedList 的浅表副本。（这些元素本身没有复制。）

相关问答

Q1: 在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();

}

}

Q2: 用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();

}

}

Q3: 用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));

}

}