「双向链表的java实现」双向循环链表java
本篇文章给大家谈谈双向链表的java实现，以及双向循环链表java对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
在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();
}
}
Java语言没有指针，怎样实现链表?
Java语言中的对象引用实际上是一个指针（这里的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
程序代码：
class Node
{
Object data;
Node next;//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。
链表的数据结构我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点，因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。如何得到当前结点呢？我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Objectd)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
链表类List的源代码如下：
package cn.javatx; import java.io.IOException;/**
* @author ljfan
*
*/
public class List {
private Node Head = null;
private Node Tail = null;
private Node Pointer = null;
private int Length = 0;public void deleteAll() {
Head = null;
Tail = null;
Pointer = null;
Length = 0;
}public void reset() {
Pointer = null;
}public boolean isEmpty() {
return (Length == 0);
}public boolean isEnd() {
if (Length == 0)
throw new java.lang.NullPointerException();
else if (Length == 1)
return true;
else
return (cursor() == Tail);
}public Object nextNode() {
if (Length == 1)
throw new java.util.NoSuchElementException();
else if (Length == 0)
throw new java.lang.NullPointerException();
else {
Node temp = cursor();
Pointer = temp;
if (temp != Tail)
return (temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}public Object currentNode() {
Node temp = cursor();
return temp.data;
}public void insert(Object d) {
Node e = new Node(d);
if (Length == 0) {
Tail = e;
Head = e;
} else {
Node temp = cursor();
e.next = temp;
if (Pointer == null)
Head = e;
else
Pointer.next = e;
}
Length++;
}public int size() {
return (Length);
}public Object remove() {
Object temp;
if (Length == 0)
throw new java.util.NoSuchElementException();
else if (Length == 1) {
temp = Head.data;
deleteAll();
} else {
Node cur = cursor();
temp = cur.data;
if (cur == Head)
Head = cur.next;
else if (cur == Tail) {
Pointer.next = null;
Tail = Pointer;
reset();
} else
Pointer.next = cur.next;
Length--;
}
return temp;
}private Node cursor() {
if (Head == null)
throw new java.lang.NullPointerException();
else if (Pointer == null)
return Head;
else
return Pointer.next;
}public static void main(String[] args) {
List a = new List();
for (int i = 1; i = 10; i++)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while (!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while (!a.isEnd()) {
a.remove();
}
a.remove();
a.reset();
if (a.isEmpty())
System.out.println("There is no Node in List n");
System.out.println("You can press return to quitn");
try {
System.in.read();
} catch (IOException e) {
}
}
}class Node {
Object data;
Node next;Node(Object d) {
data = d;
next = null;
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的现实中。
用java如何创建一个单链表和双链表
单向链表
单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构。
单向链表的初始化：这里我所讲的链表都是头结点不参与计算的，也就是说第一个结点都是头结点后面的第一个结点。所以我要先申明一点，这里我把链表的初始化放在了构造函数部分，然后析构函数负责释放头结点的内存。
单向链表的创建过程：链表的创建就是添加结点到链表的最后，开始是添加一个结点到head结点后面，然后添加一个结点到上次添加的结点后面，每次新建的结点的指针总是指向NULL指针。从上面的示意图可以看出，我们需要一个辅助指针一直指向最后一个结点，这个辅助结点就是为了让每次添加的结点都放置在最后一个位置。
单向链表插入结点过程：源代码中的的插入结点函数我设置了一个指定位置，就是在指定位置插入结点。首先，通过位置变量position让ptemp结点移动到要插入位置的前一个位置，然后接下来的过程就是和创建链表的过程是一样的，把新建的结点添加到ptemp的后面。这里变量position可以从1到链表长度加1，意思就是如果不算头结点的话有3个结点，那你的position变量就可以从1到4，这是因为ptemp指针可以到第3个结点的位置，所以新建结点的位置就可以到4了。
单向链表删除结点过程：源代码中的删除结点函数也有一个指定位置变量，为了删除指定位置的结点。和插入结点一样通过变量position把ptemp移动到要删除结点的前一个位置，然后让ptemp结点中的指针指向要删除结点后面的一个结点，也就是ptemp结点的下一个的下一个结点，虽然这个结点可能为空，但是程序还是正常运行。但是这里和插入结点不同的是变量position只能从1到链表的长度，是因为ptemp移动到最后一个结点的时候，它的下一个结点为空，所以不不需要参与删除了。
双向链表
1.听名字可能就能猜到双向链表就是链表结点包含两个指针，一个指针是指向下一个结点的，另一个指针当然就是指向上一个结点的。
2.双向链表的初始化：由于这里的链表头结点不参与计算，所以头结点的pPre指针是一直指向NULL指针的。
3.双向链表的创建过程：由于双向链表的每个结点包含两个指针那么这个时候我们就要小心处理好每一个指针的指向，要不然会有很多意想不到的错误。同样的，和单向链表的创建过程一样，需要一个辅助指针来指向最后一个结点，然后每新建一个结点，这个结点的pNext指针都是指向NULL指针的，pPre指针指向上一个结点（这是和单向链表不同的地方），然后让上一个指针的pNext指向新建的结点，这样整个链表就连接起来了。
4.双向链表插入结点过程：知道了双向链表的创建过程，那么插入结点的过程就大同小异 了，有一点需要特别注意的就是这里的变量position范围也是从1到链表长度加1，但是如果待插入的位置是最后一个位置的话，情况就不同了，看到下面的图我们可以很好的理解，因为没新建一个结点的时候都需要处理两个指针，而且新建结点的下一个结点的pPre指针就需要指向这个新建的结点，但是有可能这个新建的结点可能就已经是最后一个结点了，那么这个时候再执行
ptemp-pNext-pPre = pnew;
这条指令的时候就会报错了，因为ptemp-pNext已经是个NULL指针了，那空指针哪里还有pPre呢。因此在程序中要进行一次判断，看看结点是否是最后一个结点。
5.双向链表删除结点的过程：要注意的问题和插入结点一样，看看这个结点是否为NULL。这里就不重复了。
Java 双向链表
import java.util.*;
public class DoublyLinkedList {
//overview: a list that is doublylinked
private ListNode firstNode;
private ListNode lastNode;
//constructors:
public DoublyLinkedList(){
//EFFECTS: initialize this to be empty
firstNode = null;
lastNode = null;
}
//methods:
public synchronized void insertAtFront(Object o){
//EFFECTS: add o to the front of this
//MODIFIES: this
if(isEmpty()){
firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);
}
else{
firstNode = new ListNode(o , firstNode , lastNode);
lastNode.nextNode = firstNode;
}
}
public synchronized void insertAtBack(Object o){
//EFFECTS: add o to the back of this
//MODIFIES: this
if(isEmpty()){
firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);
}
else{
lastNode = lastNode.nextNode = new ListNode(o , lastNode , firstNode);
firstNode.prevNode = lastNode;
}
}
public synchronized Object removeFromFront() throws EmptyListException{
//EFFECTS: remove the first node of this and return the node
//MODIFIES: this
Object o = null;
if(isEmpty()){
throw new EmptyListException();
}
else{
o = firstNode.data;
if(firstNode == lastNode){
firstNode = lastNode = null;
}
else{
firstNode = firstNode.nextNode;
firstNode.prevNode = lastNode;
firstNode.nextNode = firstNode;
}
}
return o;
}
public synchronized Object removeFromBack() throws EmptyListException{
//EFFECTS: remove the last node of this and return the node
//MODIFIES: this
Object o = null;
if(isEmpty()){
throw new EmptyListException();
}
else{
o = firstNode.data;
if(firstNode == lastNode){
firstNode = lastNode = null;
}
else{
lastNode = lastNode.prevNode;
lastNode.nextNode = firstNode;
firstNode.prevNode = lastNode;
}
}
return o;
}
public synchronized Set LocalMaximum(){
//EFFECTS: 返回一个Set，其中每个元素为位置信息，在该位置处的链表元素值为极大值
//极大值是指该元素不小于其直接前驱及直接后继元素
ListNode current = firstNode;
SetInteger a = null ;
int n = 0;
while(current.nextNode != firstNode){
if(Integer.parseInt(current.data.toString()) = Integer.parseInt(current.prevNode.data.toString())
Integer.parseInt(current.data.toString()) = Integer.parseInt(current.nextNode.data.toString()))
a.add(new Integer(n));
n++;
}
return a;
}
public Iterator iterator(int direction) throws Exception{
//EFFECTS: if direction is 0 return a generator that will produce all elements of this from the first node to the last one
//else if direction is 0 return a generator that will produce all elements of this from the last node to the first one
//REQUIRES: this must not be modified while the generator is in use
if(direction == 0){
return new fl(this);
}
else if(direction == 1){
return new lf(this);
}
else{
throw new Exception("Enter the right direction!");
}
}
//inner class
private static class fl implements Iterator{
//overview: from first to last
private ListNode current;
private DoublyLinkedList y;
//constructors:
public fl(DoublyLinkedList x){
//EFFECTS: initialize this
y = x;
current = y.firstNode;
}
//methods:
public boolean hasNext(){
//EFFECTS: return true if there are more elements else return false
if(current == y.lastNode)
return false;
else
return true;
}
public Object next() throws NoSuchElementException{
//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.
// Otherwise throws NoSuchElementException
if(current == y.lastNode)
throw new NoSuchElementException("DoublyLinkedList.iterator");
else{
current = current.nextNode;
return current;
}
}
public void remove() throws UnsupportedOperationException{
throw new UnsupportedOperationException("DoublyLinkedList.iterator");
}
//end methods
//end constructors
}//end class
private static class lf implements Iterator{
//overview: from last to first
private ListNode current;
private DoublyLinkedList y;
//constructors:
public lf(DoublyLinkedList x){
//EFFECTS: initialize this
y = x;
current = y.lastNode;
}
//methods:
public boolean hasNext(){
//EFFECTS: return true if there are more elements else return false
if(current == y.firstNode)
return false;
else
return true;
}
public Object next() throws NoSuchElementException{
//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.
// Otherwise throws NoSuchElementException
if(current == y.firstNode)
throw new NoSuchElementException("DoublyLinkedList.iterator");
else{
current = current.prevNode;
return current;
}
}
public void remove() throws UnsupportedOperationException{
throw new UnsupportedOperationException("DoublyLinkedList.iterator");
}
//end methods
// end constructors
}//end class
public synchronized boolean isEmpty(){
//EFFECTS: if this is not empty retutn true else return false
return firstNode == null;
}
//end methods
//end constructors
}//end class
class ListNode{
//overview: ListNode is the node of a list
Object data;
ListNode nextNode;
ListNode prevNode;
//constructors:
public ListNode(Object o){
//EFFECTS: initialize this to be a node like(o , null)
this( o , null , null);
}
public ListNode(Object o , ListNode node1 , ListNode node2){
//EFFECTS: initialize this to be a node like(node1 , o , node2)
data = o ;
nextNode = node1;
prevNode = node2;
}
//methods:
Object getObject(){
//EFFECTS: return the object of this
return data;
}
ListNode getNext(){
//EFFECTS: return the next node of this
return nextNode;
}
ListNode getPrev(){
//EFFECTS: return the prev node of this
return prevNode;
}
//end methods
//end constructors
}//end class
class EmptyListException extends RuntimeException {
//constructors:
public EmptyListException(){
//EFFECTS: initialize an EmptyListException
super( "The list is empty" );
}
} // end class
曾经自己编过,好像...贴给你了..
双向循环链表java
我们也做这个，，你是是吧
package KeCheng1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Scanner;
//定义节点类
class NodeAnyType {
public AnyType data;
public NodeAnyType prev;
public NodeAnyType next;
public Node(AnyType d,NodeAnyType p,NodeAnyType n){
data=d;
prev=p;
next=n;}}
public class MyLinkedListAnyType {
private int theSize;
private NodeAnyType beginMarker; //头标记或头节点
private NodeAnyType endMarker; //尾标记或尾节点
public MyLinkedList(){
beginMarker=new NodeAnyType(null,endMarker,endMarker);
endMarker = new NodeAnyType(null,beginMarker,beginMarker);
beginMarker.next = endMarker;
theSize = 0;}
public int size(){
return theSize;}
public boolean add(AnyType x){
add(size(),x);
return true;}
public void add(int idx,AnyType x){
NodeAnyType p;
p=getNode(idx);
addBefore(p,x);}
private NodeAnyType getNode(int idx) {
NodeAnyType p;
if( idx 0 || idx size( ) )
throw new IndexOutOfBoundsException( );
if( idx size( ) / 2 ) {
p = beginMarker.next;
for( int i = 0; i idx; i++ )
p = p.next;}
else
{ p = endMarker;
for( int i = size( ); i idx; i-- )
p = p.prev; }
return p;}
private void addBefore( NodeAnyType p, AnyType x ) {
NodeAnyType newNode = new NodeAnyType( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;}
public AnyType remove( int idx ){
return remove( getNode(idx));}
private AnyType remove(NodeAnyType p){
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
return p.data;}
public void print(){//输出链表
for(NodeAnyTypex=beginMarker.next;x.next!=beginMarker;x=x.next)
System.out.print(x.data+" ");
System.out.print("\n");}
public AnyType get( int idx ){
return getNode( idx ).data; }
public static void main(String[] args){
MyLinkedListInteger La = new MyLinkedListInteger();
int Length;
Scanner sc = new Scanner(System.in);
System.out.println("请输入要创建的双向链表的长度：(大于6)");
Length = sc.nextInt();
System.out.println("请输入"+Length+"个元素创建La双向链表：");
for(int i=0;iLength;i++)
{La.add(sc.nextInt());}
System.out.println("输入的原La双向链表：");
La.print();
System.out.println("在双向链表的第3个位置插入20:");
La.add(3,20);
La.print();
System.out.println("删除第五位置上的数:");
La.remove(5);
La.print();
System.out.println("插入最后一个节点:99");
La.add(Length,99);
La.print();
System.out.println("插入第一个节点0:");
La.add(0,0);
La.print();
System.out.println("就地逆置:");
int M=Length+2;
int b=0;
for(Length=Length+1;Length=0;Length--){
int a=La.get(M-1);
La.add(b,a);
b=b+1;
La.remove(M);
}
La.print();
}
}
关于双向链表的java实现和双向循环链表java的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-12-19，除非注明，否则均为原创文章，转载请注明出处。