欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图解单链表(关于单链表,看这一篇文章就够了)

程序员文章站 2022-05-01 10:10:07
...

Hello,小伙伴们大家好,我是才辰,首先祝大家国庆假期快乐! 图解单链表(关于单链表,看这一篇文章就够了)

这次会为大家带来链表的专题的讲解,这篇文章是专题系列的第一篇,分享一下最基础最常用的单链表

单向链表是链表中最常用的一种,一个列表节点有两个字段,即数据域指针域。在单向链表中,指向第一个节点的节点称为“头结点”,最后一个节点的指针域设为null。

例如:列表A={1,3,1,4,5,2,1}的单向链表数据结构如下:

图解单链表(关于单链表,看这一篇文章就够了) 在Java语言中,声明一个Node节点类的代码如下:

class Node{
int data;
Node next;
//构造函数
public Node(int data1) { data=data1; next=null; } } 

为方便大家查看,我为下面的内容做了一个目录。

  • 建立单向链表
  • 单向链表节点的删除
  • 单项链表的节点插入
  • 单项链表的反转
  • 单向链表的串联
  • 多项式的链表表示法

1 建立单向链表

现在,我们使用Java语言建立一个简单的单向链表。
每个节点的数据为学生的学号(int)、姓名(String)、成绩(int).如下:

学号 姓名 成绩
01 小明 85
02 小明明 86
03 小红 87
04 小红红 80
05 小明 70

不要问为什么有两个小明,问就是重名了。

让每个节点包含一个学生数据,并且包含指向下一个节点的指针,使所有数据形成一个链表结构

图解单链表(关于单链表,看这一篇文章就够了) 我们先建立链表部分代码,在链表中定义两个Node节点类,分别指向链表第一个和最后一个节点,还定义了基本的3个方法:

方法名称 说明
public boolean isEmpty() 判断链表是否为空
public void print() 打印链表节点
public void insert(int num1,String name1,int score1) 将节点数据插入到链表

代码如下:(有详细注解)

import java.util.Scanner;
import java.io.*;
//定义节点
class Node{
int num;//学号 int score;//成绩 String name;//姓名 Node next;//指向下一节点 public Node(int num1,String name1,int score1) { num=num1; score=score1; name=name1; next=null; }  } //构造链表 class LinkedList { private Node first; private Node last; //判断链表是否为空 public boolean isEmpty() { return first==null; } //打印链表节点 public void print() { Node cur=first; while(cur!=null) { System.out.println(cur.num+" "+cur.name+" "+cur.score); cur=cur.next; } } //插入节点 public void insert(int num1,String name1,int score1) { Node newNode=new Node(num1,name1,score1); //如果链表为空,头指针和尾指针都指向该节点 if(isEmpty()) { first=newNode; last=newNode; } //如果不为空,尾节点指向该节点,并更新尾节点 else { last.next=newNode; last=newNode;  } } } 

接着我们在主函数中输入学生信息,并将节点信息打印出来

public class Main {
public static void main(String[] args) {
//建立5个学生成绩的单向链表
Scanner scan=new Scanner(System.in);
int num;
String name; int score; LinkedList list=new LinkedList(); //输入数据 System.out.println("请输入数据"); for(int i=0;i<5;i++) { num=scan.nextInt(); name=scan.next(); score=scan.nextInt(); list.insert(num,name,score); } //打印数据 System.out.println("节点数据如下"); list.print(); } }  

执行结果:

图解单链表(关于单链表,看这一篇文章就够了)

2 单链表节点的删除

根据待删除节点在链表中的位置不同,有如下三种情形:

  1. 待删除节点是链表的第一个节点

此时,只要把头结点指针指向第二个节点即可。

if(first.num==delNode.num)
{
     first=first.next;
}
图解单链表(关于单链表,看这一篇文章就够了)
  1. 待删除节点是链表的中间节点
newNode=first;
tmp=first;
while(newNode.num!=delNode.num)
{
   tmp=newNode;
 newNode=newNode.next; }  tmp.next=newNode.next; 

图解单链表(关于单链表,看这一篇文章就够了) 3. 待删除节点是链表的最后一个节点

newNode=first;
while(newNode.next!=last)
newNode=newNode.next;
newNode.next=last.next;
//更新最后一个节点
last=newNode; 

图解单链表(关于单链表,看这一篇文章就够了) 实现代码

public void delete(Node delNode)
  {
   Node newNode;
   Node tmp;
   //删除链表第一个节点
 if(first.num==delNode.num)  {  first=first.next;  }  //删除链表最后一个节点  else if(last.num==delNode.num)  {  newNode=first;  while(newNode.next!=last)  newNode=newNode.next;  newNode.next=last.next;  //更新最后一个节点  last=newNode;   }  //删除中间节点   else  {  newNode=first;  tmp=first;  while(newNode.num!=delNode.num)  {  tmp=newNode;  newNode=newNode.next;  }  tmp.next=newNode.next;  }   } 

在主函数中测试时,只需输入待删除节点的数据,构造一个新的节点,接着调用delete函数
//输入要删除学生成绩的学号System.out.println("输入删除节点数据");
int num1=scan.nextInt();
String name1=scan.next();
int score1=scan.nextInt();
//构造节点
Node delNode=new Node(num1,name1,score1); //调用delete list.delete(delNode);  

结果如下: 图解单链表(关于单链表,看这一篇文章就够了)

3 单链表的节点插入

和节点的删除类似,也是按照位置的不同分为3种情况:

  1. 插入位置在链表的头部 这时只需将新节点的指针指向第一个节点,更新头结点
图解单链表(关于单链表,看这一篇文章就够了)
  1. 插入位置在链表中间

如果插入位置在x与y之间,则将x指向该节点,该节点指针指向y.

图解单链表(关于单链表,看这一篇文章就够了) 3. 插入位置在链表尾部

将链表最后一个节点的指针指向该节点,并更新尾节点

图解单链表(关于单链表,看这一篇文章就够了)

4 单向链表的反转

要将单链表反转,需要使用三个指针变量,before,current,last.

图解单链表(关于单链表,看这一篇文章就够了)

代码如下:

class reverseLinkedList extends LinkedList
{
 
 public void reverse_print()
 {
 Node current=first;  Node before=null;  System.out.println("反转后的链表:");  while(current!=null)  {  last=before;  before=current;  current=current.next;  before.next=last;   }  current=before;  while(current!=null)  {  System.out.println(current.num+" "+current.name+" "+current.score);  current=current.next;  }  } } 

结果如下: 图解单链表(关于单链表,看这一篇文章就够了)

5 单向链表的串联

实现单向链表的串联,指向将第一个链表最后一个节点指向第二个链表的第一个节点即可。

图解单链表(关于单链表,看这一篇文章就够了) 实现代码:


 public LinkedList concatenate(LinkedList h1,LinkedList h2)
  {
   LinkedList ptr;
   ptr=h1;
 while(ptr.last.next!=null)  ptr.last=ptr.last.next;  ptr.last.next=h2.first;  return h1;   } 

6 多项式的链表表示法

多项式的链表表示法主要是存储非零项目,并且每一项均符合以下数据结构:

coef (变量系数) exp(变量指数) link(指向下一节点)

例如;3x*x+6x-2的表示方法为:

图解单链表(关于单链表,看这一篇文章就够了)

表示多项式的加法时,直接让指数相同的系数相加,指数只在一方的直接放到新链表中,例如

行 A=3x*x+6x-2

B=4(x*x)*x+16x+8

求A+B的算法如下

图解单链表(关于单链表,看这一篇文章就够了)

至于实现代码,大家可以自己写一下。

8 小结

好了,以上就是本文的主要内容了。接下来会继续分享其他的链表结构,请大家持续关注!

那我们下一篇文章再见!


                  文:才辰
                排版:才辰
图解单链表(关于单链表,看这一篇文章就够了)
关注【编程365】学习更多计算机基础+算法知识

本文使用 mdnice 排版