在Java中如何实现双向链表

发布网友 发布时间：2022-04-21 17:35

我来回答

共3个回答

懂视网 时间：2022-04-15 12:22

　　

　　链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语言和C＋＋语言中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在Java语言中不能实现链表，其实不然，Java语言比C和C＋＋更容易实现链表结构。Java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。

　　class Node
　　{
　　Object data;
　　Node next;//指向下一个结点
　　}

　　将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。下图是这种链表的示意图：

热心网友 时间：2022-04-15 09:30

双向链表：就是有双向指针，即双向的链域。
链结点的结构：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
双向链表不必是双端链表(持有对最后一个链结点的引用)，双端链表插入时是双向的。
有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的。
/**
* 双向链表
*/
public class DoublyLinkedList<t> {
private Link<t> head; //首结点
private Link<t> 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) {// 插入 到 链头
Link<t> newLink = new Link<t>(data);
if (isEmpty()) {//为空时，第1次插入的新结点为尾结点
rear = newLink;
} else {
head.previous = newLink; //旧头结点的上结点等于新结点
}
newLink.next = head; //新结点的下结点旧头结点
head = newLink; //赋值后，头结点的下结点是旧头结点，上结点null
}
public void insertLast(T data) {//在链尾 插入
Link<t> newLink = new Link<t>(data);
if (isEmpty()) {
head = newLink;
} else {
rear.next = newLink;
}
newLink.previous = rear;
rear = newLink; //赋值后，尾结点的上结点是旧尾结点，下结点null
}
public T deleteHead() {//删除 链头
if (isEmpty()) return null;
Link<t> temp = head;
head = head.next; //变更首结点，为下一结点
if (head != null) {
head.previous = null;
} else {
rear = null;
}
return temp.data;
}
public T deleteRear() {//删除 链尾
if (isEmpty()) return null;
Link<t> 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;
}
Link<t> 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;
}
Link<t> 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;
}
Link<t> current = head;
while (!current.data.equals(key)) {
current = current.next;
if (current == null) {
return false;
}
}
Link<t> newLink = new Link<t>(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):");
Link<t> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayList4Rear() {//从尾开始遍历
System.out.println("List (last-->first):");
Link<t> current = rear;
while (current != null) {
current.displayLink();
current = current.previous;
}
}

class Link<t> {//链结点
T data; //数据域
Link<t> next; //后继指针，结点 链域
Link<t> previous; //前驱指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
DoublyLinkedList<integer> list = new DoublyLinkedList<integer>();
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();
}
}

热心网友 时间：2022-04-15 10:48

自定异常类：Java代码 public class MyException extends Exception { public MyException(){}; public MyException(String msg){ super(msg); } } 链表结点对像：Java代码 public class Node { public Node previou=null;//前结点指针 public Node next=null; //后结点指针 public Object value;//结点值 Node(Object value){ this.value=value; } } 链表对像： Java代码 public class DoubleLinked { private Node head;//链表头 DoubleLinked(){ } /** * 判断是否还有下一个结点，没有则为链表的尾结点 * @param node * @return */ public boolean hasNext(Node node){ if(node.next==null) return false; return true; } /** * 判断是否有上一个结点，没有则为链表的头结点 * @param node * @return */ public boolean hasPrev(Node node){ if(node.previou==null) return false; return true; } /** * 获取链表头元素 * @return * @throws MyException */ public Node getHead() throws MyException{ if(head==null){ throw new MyException("链表为空"); } return head; } /** * 获取上一个接点 * @param node * @return */ public Node getPrev(Node node){ return node.previou; } /** * 获取下一个结点 * @param node * @return */ public Node getNext(Node node){ return node.next; } /** * 根据索引获取结点 * @param index：结点索引 * @return * @throws MyException */ public Node getNode(int index) throws MyException{ Node curNode=null; Node next=null; Node node=null; if(head==null){ throw new MyException("链表为空"); }else{ curNode=head; for(int i=0;i<index;i++){ if(curNode==null){ throw new MyException("你要获取的元素索引大于链表长度"); }else{ node=curNode; if(hasNext(curNode)){ next=curNode.next; curNode=next; }else{ curNode=null; } } } } return node; }/** * 获取最后一个结点 * @return * @throws MyException */ public Node getLast() throws MyException{ Node curNode=null; Node next=null; Node last=null; boolean flag=true; if(head==null){ throw new MyException("链表为空"); }else{ curNode=head; while(flag){ if(hasNext(curNode)){ next=curNode.next; curNode=next; }else{ last=curNode; flag=false; } } } return last; } /** * 在链表头添加新结点 * @param node */ public void addHead(Node node){ if(head==null){ head=node; }else{ node.next=head; head.previou=node; head=node; } } /** * 在链表末尾处添加新结点 * @param node * @throws MyException */ public void addLast(Node node) throws MyException{ if(head==null){ head=node; }else{ Node last=this.getLast(); last.next=node; node.previou=last; } } /** * 在链表中间插入新结点 * @param node * @throws MyException */ public void insertNode(int index,Node node) throws MyException{ Node indexNode=this.getNode(index); Node prev=indexNode.previou; prev.next=node; node.previou=prev; node.next=indexNode; indexNode.previou=node; } /** * 删除链表头结点 * @return * @throws MyException */ public Node deleteHead() throws MyException{ Node head=this.getHead(); if(hasNext(head)){ Node next=head.next; this.head=next; next.previou=null; } return head; } /** * 删除链表的最后一个结点 * @return * @throws MyException */ public Node deleteLast() throws MyException{ Node last=this.getLast(); Node prev=last.previou; if(prev==null){ this.head=null; }else{ prev.next=null; } return last; } /** * 根据索引删除链表结点 * @param index * @return * @throws MyException */ public Node deleteNode(int index) throws MyException{ Node node=this.getNode(index); Node prev=node.previou; Node next=node.next; if(prev==null && next!=null){ this.head=next; next.previou=null; } if(prev!=null && next==null){ prev.next=null; } if(prev==null && next==null){ this.head=null; } if(prev!=null && next!=null){ prev.next=next; next.previou=prev; } return node; } } :!: