欢迎访问欧博网址!

首页科技正文

欧博亚洲官网开户网址:线性表的链式存储--单链表

admin2020-08-3079

Java之线性表的链式存储——单链表

我们都知道,线性表的存储结构分为两种,顺序存储结构和链式存储结构,线性表的分类可以参考下图来学习影象。今天我们主要来学习一下链式存储结构。

一、链式存储先容

"链式存储结构,地址可以延续也可以不延续的存储单元存储数据元素"——来自界说。

实在,你可以想象这样一个场景,你想找一个人(他的名字叫小谭),于是你首先去问 A , A 说他不知道,然则他说 B 可能知道,并告诉了你 B 在那里,于是你找到 B ,B 说他不知道,然则他说 C 可能知道,并告诉了你 C 的地址,于是你去找到 C ,C 真的知道小谭在那边。

上面场景实在可以辅助我们去明白链表,实在每一个链表都包罗多个节点,节点又包罗两个部门,一个是数据域(储存节点含有的信息),一个是指针域(储存下一个节点或者上一个节点的地址),而这个指针域就相当于你去问B,B知道C的地址,这个指针域就是存放的 C 的地址。

链表下面实在又细分了3种:单链表、双向链表和循环链表。今天我们先讲单链表。

二、单链表先容

什么是单链表呢?单链表就是每一个节点只有一个指针域的链表。如下图所示,就是一个带头节点的单链表。下面我们需要知道什么是头指针,头节点和首元节点。

头指针:指向链表节点的第一个节点的指针

头节点:指在链表的首元节点之前附设的一个节点

首元节点:指在链表中存储第一个现实数据元素的节点(好比上图的 a1 节点)

三、单链表的建立

单链表的建立有两种方式,分别是头插法和尾插法。

1、头插法

头插法,顾名思义就是把新元素插入到头部的位置,每次新加的元素都作为链表的第一个节点。那么头插入法在Java中怎么实现呢。首先我们需要界说一个节点,如下

public class ListNode {
  public int val; //数据域
  public ListNode next;//指针域
}

然后我们就建立一个头指针(不带头节点)

//元素个数
int n = 5;
//建立一个头指针
ListNode headNode = new ListNode();
//头插入法
headNode= createHead(headNode, n);

然后建立一个私有方式去实现头插法,这里我们插入5个新元素,头插入的焦点是要先断开首元节点和头指针的毗邻,也就是需要先将原来首元节点的地址存放到新节点的指针域里,也就是 newNode.next = headNode.next,然后再让头指针指向新的节点 headNode.next = newNode,这两步是头插入的焦点,一定要明白。

/**
 * 头插法
 * 新的节点放在头节点的后面,之前的就放在新节点的后面
 * @param headNode 头指针
 * @return
 */
private static ListNode createHead(ListNode headNode, int n) {
  //插入5个新节点
  for (int i = 1; i <= n; i++) {
    ListNode newNode = new ListNode();
    newNode.val = i;
    //将之前的所有节点指向新的节点(也就是新节点指向之前的所有节点)
    newNode.next = headNode.next;
    //将头指针指向新的节点
    headNode.next = newNode;
  }
  return headNode;
}

最后我把链表打印输出一下(实在也是单链表的遍历),判断条件就是只有当指针域为空的时刻才是最后一个节点。

private static void printLinkedList(ListNode headNode) {
  int countNode = 0;
  while (headNode.next != null){
    countNode++;
    System.out.println(headNode.next.val);
    headNode = headNode.next;
  }
  System.out.println("该单链表的节点总数:" +countNode);
}

最后的输出效果显然是逆序,由于没一个新的元素都是从头部插入的,自然第一个就是最后一个,最后一个就是第一个:

2、尾插法

尾插法,顾名思义就是把新元素插入到尾部的位置(也就是最后一个位置),每次新加的元素都作为链表的第最后节点。那么尾插法在 Java 中怎么实现呢,这里照样接纳不带头节点的实现方式,头节点和头指针和头插入的实现方式一样,这里我就直接将若何实现:

/**
 * 尾插法
 * 找到链表的末尾结点,把新添加的数据作为末尾结点的后续结点
 * @param headNode
 */
private static ListNode createByTail(ListNode headNode, int n) {
  //让尾指针也指向头指针
  ListNode tailNode = headNode;
  for (int i = 1; i <= n; i++) {
    ListNode newNode = new ListNode();
    newNode.val = i;
    newNode.next = null;

    //插入到链表尾部
    tailNode.next = newNode;
    //指向新的尾节点,tailer永远存储最后一个节点的地址
    tailNode = newNode;

  }
  return headNode;
}

和头插入差别的是,我们需要声明一个尾指针来辅助我们实现,最最先,尾指针指向头指针,每插入一个元素,尾指针就后移一下,这里我们来讲一下原理:每次往末尾新加一个节点,我们就需要把原来的毗邻断开,那怎么断开呢,我们首先需要让尾指针指向新的节点,也就是 tailNode.next = newNode; 然后再让尾指针后移一个位置,让尾指针指向最后一个节点。也就是尾指针始终指向最后一个节点,最后将头指针返回,输出最后效果:

四、单链表的删除

既然单链表建立好了,怎么在链表内里删除元素呢,单链表的删除,我分为了两种情形删除,分别是删除第i个节点和删除指定元素的节点。

1、删除第i个节点

我们可以先来理一下思绪:在单链内外,节点与节点之间都是通过指针域链接起来的,以是若是我们想实现删除的操作,现实上是需要我们去改变响应指针域对应得地址的。当想去删除第i个元素的时刻,好比要删除上图的第3个元素(也就是3),现实上我们要做的就是要让2号元素指向4号元素(实在就是需要修改2号元素的指针域,让2号元素的指针域存储4号元素)。那么怎么做才气实现这一步呢?很显然,要实现这个步骤,我们必须要找到4号元素和2号元素,然则再仔细想一下,实在我们只需要找到2号元素就可以了,由于4号元素的地址存储再2号的下一个元素的指针域内里。

以是综上所述剖析我们可以得出删除的两个焦点步骤:

1.删除第i个节点,需要先找到第 i-1 个个节点,也就是第i个节点的前一个节点;

2.然后让第 i-1 个节点指向第 i-1 个节点的下下个节点

下面的代码详细实现了怎么删除第i个元素。

/**
 * 删除第i个节点
 * 1,2 4,4,5
 * 删除之后应该是1,2,4,5
 * @param headNode
 * @param index
 * @return
 */
public static ListNode deleteNodeByIndex(ListNode headNode, int index) {
  int count = 1;
  //将引用给它
  ListNode preNode = headNode;
  //看计数器是不是到了i-1,若是到了i-1,就找到了第i-1个节点
  while (preNode.next != null && count <= index -1){
    //寻找要删除的当前节点的前一个节点
    count++;
    preNode = preNode.next;
  }
  if (preNode != null){
    preNode.next = preNode.next.next;
  }
  return headNode;
}

2、删除指定元素的谁人节点

删除指定元素节点的实现方式有两种,第一种就是先找到指定元素对应的链表的位置( index ),然后再根据删除第 i 个节点的思绪删除即可。实现方式如下图所示:

/**
 * 删除链表指定数值的节点
 * @param headNode
 * @param val
 * @return
 */
private static ListNode deleteNodeByNum(ListNode headNode, int val) {
  ListNode deleteOne = headNode;
  int countByDeleteOne = 1;
  while (deleteOne.next != null){
    if (deleteOne.next.val == val){
      deleteOne = deleteOne.next;
      break;
    }
    countByDeleteOne ++;
    deleteOne = deleteOne.next;
  }
  return deleteNodeByIndex(headNode, countByDeleteOne);
}

第二种方式的实现就很精妙(条件是此节点不是尾节点)

public void deleteNode(ListNode node) {
  //删除node即通过将后面的值赋给node,然后更改node的指针指向下下一个结点即可
  node.val = node.next.val;
  node.next = node.next.next;
}

五、单链表的查询(及修改)

单链表的查询实现很简单,就是遍历当前单链表,然后用一个计数器累加到当前下标,那么当前的这个节点就是要查询的谁人节点,然后再返回即可,固然需要判断传过来的这个下标是否正当。固然若是需要修改,就需要把当前找到的节点的数据域重新赋上需要修改的值即可,这里就不上代码了。详细实现如下:

private static ListNode searchLinkedList(ListNode headNode, int index) {
  //若是下标是不正当的下标就示意找不到
  if (index < 1 || index > getLinkedListLength(headNode)){
      return null;
  }
  for (int i = 0; i < index; i++) {
    headNode = headNode.next;
  }
  return headNode;
}

获取单链表的长度(注重我这里界说的 headNode 是头指针不是头节点)

/**
 * 求单链表长度
 * @param headNode
 * @return
 */
private static int getLinkedListLength(ListNode headNode) {
  int countNode = 0;
  while (headNode.next != null){
    countNode++;
    headNode = headNode.next;
  }
 return countNode;
}

六、小结

单链表的相关操作就解说完了,实在通过上面临单链表的相关操作,我们不难发现,单链表的删除和插入实在很利便,只需要改变指针的指向就可以完成,然则查找元素的时刻就对照贫苦,由于在查找的时刻,需要把整个链表从头至尾遍历一次。

民众号:良许Linux

有收获?希望老铁们来个三连击,给更多的人看到这篇文章

,

欧博客户端

欢迎进入欧博客户端(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

转载声明:本站发布文章及版权归原作者所有,转载本站文章请注明文章来源!

本文链接:https://www.chinadsn9.com/post/723.html

网友评论

1条评论
  • 2020-08-30 00:00:45

    欧博亚洲电脑版下载欢迎进入欧博亚洲电脑版下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。今日签到

最新评论

  • 环球UG 10/19 说:

    Allbet开户欢迎进入Allbet开户(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。会不断进步的

  • AllbetGmaing下载 10/19 说:

    欧博APP欢迎进入欧博APP(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。踩一下,溜了

  • 联博以太坊高度 10/19 说:

    联博API接口www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。感觉已经火了

  • 皇冠APP下载 10/18 说:

    欧博手机版欢迎进入欧博手机版(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。哈哈,交流起来

  • UG环球网址 10/18 说:

    Allbet客户端下载欢迎进入Allbet客户端下载(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。可以,在看

  • Allbet登录网址 10/18 说:

    欧博亚洲官网开户网址欢迎进入欧博亚洲官网开户网址(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。找了好久,心心念念的

  • 环球UG开户 10/17 说:

    欧博allbet注册欢迎进入欧博allbet注册(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。想穿越进去

  • Allbet代理 10/16 说:

    平心在线欢迎进入平心在线官网(原诚信在线、阳光在线)。平心在线官网开www.px111.net放平心在线会员登录网址、平心在线代理后台网址、平心在线APP下载、平心在线电脑客户端下载、平心在线企业邮局等业务。很值,优点无数