「链表java删除」链表的删除函数
本篇文章给大家谈谈链表java删除，以及链表的删除函数对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
用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语言实现单向链表
1.先定义一个节点类
package com.buren;
public class IntNode {
//定义一个节点类
int
info;
//定义属性，节点中的值
IntNode next;
//定义指向下一个节点的属性
public IntNode(int
i){ //构造一个next为空的节点
this(i,null);
}
public IntNode(int i,IntNode
n){ //构造值为i指向n的节点
info=i;
next=n;
}
}
2.再定义一个链表类，这是主要部分
package com.buren;
public class IntSLList {
private IntNode head,tail;
//定义指向头结点和尾结点的指针，
//如果大家看着这个不像指针的话，那就需要对指针有更深刻的了解
public
IntSLList(){
//定义一个空节点
head=tail=null;
}
public boolean
isEmpty(){
//判断节点是否为空
return
head==null;
//这行代码看起来似乎很神奇，其实真的很神奇，偶是服了
}
public void addToHead(int el){
//将el插入到头结点前
head=new
IntNode(el,head);
//将节点插入到头结点前，作为新的投节点
if(head==tail){
//给空链表插入节点时
tail=head;
//头结点和尾结点指向同一个节点
}
}
public void addToTail(int
el){
//向链表的尾部增加结点
if(!isEmpty()){
//判断链表是否为空
tail.next=new
IntNode(el);
//新建立一个值为el的节点，将链表的尾结点指向新节点
tail=tail.next;
//更新尾指针的指向
}else{
head=tail=new
IntNode(el);
//如果链表为空，新建立一个节点，将头尾指针同时指向这个节点
}
}
public int
deleteFromHead(){
//删除头结点，将节点信息返回
int
el=head.info;
//取出节点信息
if(head==tail){
//如果链表中只有一个节点
head=tail=null;
//删除这一个节点
}else{
head=head.next;
//如果链表中不止一个节点，将头结点的下一个节点作为头结点
}
return
el;
//返回原头结点的值
}
public int
deleteFromTail(){
//删除尾结点，返回尾结点的信息
int
el=tail.info;
//取出尾结点的值
if(head==tail){
// 如果链表中只有一个节点
head=tail=null;
//删除这个节点
}else{
IntNode
temp;
//定义中间变量
for(temp=head;temp.next!=tail;temp=temp.next);
//找出尾结点的前一个节点，注意最后的分号，
//这个for循环是没有循环体的，目的在于找出尾结点的前一个节点
//在整个程序中用了很多次这样的写法，相当经典啊
tail=temp;
//将找出来的节点作为尾结点，删除原来的尾结点
tail.next=null;
//将新尾结点的指向设为空
}
return
el;
//返回原尾结点的信息
}
public void
printAll(){
//打印链表中所有节点的信息
if(isEmpty()){
//如果链表为空
System.out.println("This
list is
empty!");
//输出提示信息
return;
//返回到调用的地方
}
if(head==tail){
//当链表中只有一个节点时
System.out.println(head.info);
//输出这个节点的信息，就是头结点的信息
return;
}
IntNode
temp;
//定义一个中间变量
for(temp=head;temp!=null;temp=temp.next){
//遍历整个链表
System.out.print(temp.info+"
");
//输出每个节点的信息
}
System.out.println();
//输出一个换行，可以没有这一行
}
public boolean isInList(int
el){
//判断el是否存在于链表中
IntNode
temp;
//定义一个中间变量
for(temp=head;temp!=null
temp.info!=el;temp=temp.next);
//将el找出来，注意最后的分
return
temp!=null;
// 如果存在返回true，否则返回flase，这两行代码很有思想
}
public void delete(int
el){
//删除链表中值为el的节点
if(head.info==el
head==tail){
//如果只有一个节点，并且节点的值为el
head=tail=null;
//删除这个节点
}else
if(head.info==el){
// 不止一个节点，而头结点的值就是el
head=head.next;
//删除头结点
}else{
IntNode
pred,temp;
//定义两个中间变量
for(pred=head,temp=head.next;temp.info!=el
temp.next!=null;pred=pred.next,temp=temp.next);
//跟上面的类似，自己琢磨吧，也是要注意最后的分号
pred.next=temp.next;
//将temp指向的节点删除，最好画一个链表的图，有助于理解
if(temp==tail){
//如果temp指向的节点是尾结点
tail=pred;
//将pred指向的节点设为尾结点，
}
}
}
//下面这个方法是在链表中值为el1的节点前面插入一个值为el2的节点，
//用类似的思想可以再写一个在链表中值为el1的节点后面插入一个值为el2的节点
public boolean insertToList(int el1,int
el2){
//定义一个插入节点的方法，插入成功返回true，否则返回false
IntNode
pred,temp; //定义两个中间变量
if(isEmpty()){
//判断链表是否为空
return
false;
//如果链表为空就直接返回false
}
if(head.info==el1
head==tail){
//如果链表中只有一个节点，并且这个节点的值是el1
head=new
IntNode(el2,head);
//新建立一个节点
return
true;
}else if(head.info==el1){
IntNode t=new
IntNode(el2);
t.next=head;
head=t;
return
true;
}else{
for(pred=head,temp=head.next;temp!=null
temp.info!=el1;pred=pred.next,temp=temp.next);
if(temp!=null){
IntNode
a=new IntNode(el2);
pred.next=a;
a.next=temp;
return
true;
}else{
System.out.println(el1+"
NOT EXEISTS!");
return
false;
}
}
}
3.下面是测试代码
public static void main(String[] args){
IntSLList test=new
IntSLList();
//test.addToHead(7);
test.addToTail(7);
System.out.println(test.insertToList(7,5));
test.printAll();
System.out.println(test.isInList(123));
}
}
java 中什么是链表,链表结构有什么好处。
比如linkedlist,链表的好处是删除快，但是在增添的时候速度慢，普通arraylist，linklist,10w个以上数据的读写中就比较容易看出速度上的差别了。 arraylist是普通数组，在删除时要移位，数量级大的情况下速度非常慢。linkedlist在java实现中应为模拟链表结构，在添加操作时增加了很多运算次数，但是删除时不需要移位，只需要重新标记地址，所以删除比较快。
以上为例子，其实基于链表的集合还有不少，java方便的提供了很多api，其实数据结构都是一样的，无论是哪个语言实现。
求java 单链表基本操作的实现
/*
注意：链表的结点数量用size表示，结点的位置为0~size-1
*/
import java.util.Scanner;
public class Test7 {
public static void main(String[] args) {
try{
LinkList list = new LinkList();
Integer value;
int pos = 0;
Scanner input = new Scanner(System.in);
String choice = null;
//测试A
while(true){
System.out.print("请输入待插入结点的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
if(list.addAt(pos, value) == true){
System.out.println("插入值为 " + value + " 的结点到当前链表成功!");
pos++;
}
else{
System.out.println("插入结点失败!");
}
}
System.out.print("当前链表所有结点：");
list.listAll();
//测试B
while(true){
System.out.print("请输入待查询结点的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
pos = list.findByValue(value);
if(pos == -1){
System.out.println("当前链表中不存在值为 " + value + " 的结点");
}
else{
System.out.println("值为 " + value + " 的结点在当前链表中的位置为 " + pos);
}
}
//测试C
while(true){
System.out.print("请输入待删除结点的位置[0~" + (list.getSize()-1) + "](x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
pos = Integer.valueOf(choice);
if(list.removeAt(pos) == true){
System.out.println("删除当前链表中 " + pos + " 位置的结点成功!");
}
else{
System.out.println("删除结点失败!");
}
}
System.out.print("当前链表所有结点：");
list.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
}
/**
* 链表结点类
*/
class Node{
private Object data; //链表结点的数据域
private Node next; //链表结点的指针域，指向直接后继结点
public Node(){
data = null;
next = null;
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
public Object getData(){
return this.data;
}
public void setData(Object data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public void setNext(Node next){
this.next = next;
}
}
/**
* 链表类
*/
class LinkList{
private Node head = null; //头结点指针
private int size = 0;
public LinkList(){
head = new Node();
size = 0;
}
//在i位置插入元素elem
public boolean addAt(int i, Object elem) {
if(i 0 || i size){
return false;
}
Node pre,curr;
int pos;
for(pre=head; i0 pre.getNext()!=null; i--,pre=pre.getNext());
curr = new Node(elem, pre.getNext());
pre.setNext(curr);
size++;
return true;
}
//删除i位置的元素
public boolean removeAt(int i) {
if(i 0 || i = size){
return false;
}
Node pre,curr;
for(pre=head; i0 pre.getNext()!=null; i--,pre=pre.getNext());
curr = pre.getNext();
pre.setNext(curr.getNext());
size--;
return true;
}
//根据值value查询结点是否存在，若存在返回位置，否则返回-1
public int findByValue(Object value){
Node curr;
int pos;
for(pos=0,curr=head.getNext(); curr!=null; pos++,curr=curr.getNext()){
if(curr.getData().toString().equals(value.toString())){
break;
}
}
if(curr==null){
return -1;
}
return pos;
//return (curr!=null ? pos : -1);
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return (size==0);
}
public void listAll(){
for(Node curr=head.getNext(); curr!=null; curr=curr.getNext()){
System.out.print(curr.getData() + "\t");
}
System.out.println();
}
}
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删除的信息别忘了在本站进行查找喔。
发布于：2022-12-25，除非注明，否则均为原创文章，转载请注明出处。