「java双向链表是什么」java单向链表有哪些

博主：adminadmin 2023-01-15 11:03:06 404

本篇文章给大家谈谈java双向链表是什么，以及java单向链表有哪些对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

java中 双向链表是什么意思啊，是用来干啥的啊，求大神解答？谢谢

采用双向循环链表作为数据结构

1 新元素的下一个指向header

2 新元素的上一个指向header的上一个

3 新元素的上一个的下一个指向新元素

4 新元素的下一个的上一个指向新元素

一般LinkedList是采用双向循环链表，无需扩容，添加元素添加到最后即可

java 中的LinkedList 是双向循环列表吗？

源代码中:

public void addLast(E e) {

addBefore(e, header);

}

将指定元素添加到此列表的结尾

public boolean add(E e) {

addBefore(e, header);

return true;

}

所以,add是向列表尾加的

看了一下addBefore方法

应该是双链表结构 不是循环双链表

用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 链表是什么意思

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

class Node

{

Object data;

Node next;//指向下一个结点

}

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

链表的数据结构

我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。

链表类List的源代码如下：

import java.io.*;

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.in.println("You can press return to quit\n");

try

{

System.in.read();

//确保用户看清程序运行结果

}

catch(IOException e)

{}

}

}

class Node

/*构成链表的结点定义*/

{

Object data;

Node next;

Node(Object d)

{

data=d;

next=null;

}

}

读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。

可以用这样的代码来实现：

class Node

{

Object data;

Node next;

Node previous;

Node(Object d)

{

data=d;

next=null;

previous=null;

}

}

当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加改动即可。

java中链表是指java.util包中的LinkedList类吗

链表指的是一种数据存储结构，java.util.LinkedList是JAVA自己实现的一个双向链表，自定义链表的话可以参考LinkedList类的源码

java双向链表是什么的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java单向链表有哪些、java双向链表是什么的信息别忘了在本站进行查找喔。

标签：