java双向链表,java双向链表反转

本文目录一览：

• 1、在java中实现双向链表的 clone() 方法
• 2、用JAVA语言，编写一个链表类(双向链表),实现插入,删除,查找操作。新手，要俗易懂些，最好自己调适通过。急
• 3、用JAVA语言解决：编写一个链表类(双向链表),实现插入,删除,查找操作
• 4、java中 双向链表是什么意思啊，是用来干啥的啊，求大神解答？谢谢
• 5、在Java中如何实现双向链表?
• 6、在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();

}

}