JAVA 链表头部插入和尾部插入方法
最编程
2024-06-11 11:57:52
...
1、链表概念
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表是由值和地址组成,地址指向下一个值的地址,如下图所示
我们先定义一个节点类Listnode,里面包含值和地址属性,再通过构造器传值为这个值在内存中申请一块区域。代码如下:
public class Listnode {
//链表中一个节点的值属性
public int value;
//链表中一个节点的指针域属性,指向下一个值的地址,因为下一块区域是Listnode类型的所以next也是Listnode类型
public Listnode next;
//构造器,通过值传递给value赋值
public Listnode(int n) {
this.value=n;
}
}
2.头插法
先创建一个链表类Linklist.
头插法的思路是定义一个头指针Listnode head=null,把第一个节点的地址通过值传递给它,再创建节点时,让这个新节点的next指针指向旧节点,再让这个头指针指向新节点。如下图:
头插法看如下代码:
public class LinkList {
ListNode head = null;
public void headInsert(int value) {
//要插入的新节点
ListNode newListNode = new ListNode(value);
//如果第一次插入节点,此时head为null,直接将新节点赋值给head
if (head == null) {
head = newListNode;
return;
}
//如果不是第一次插入节点
//将新节点的next指向旧节点,因为旧节点通过值传递的方式传给head
newListNode.next = head;
//新节点通过值传递的方式传给head
head = newListNode;
}
}
3.尾插法
尾插法的思路是先定义一个游标temp,游标从头结点head开始,如果它的next指针域不是null,就让游标指向下一个,直到游标指向next指针域为null,然后在这个节点后插入新的节点。
尾插法代码如下:
public class LinkList {
ListNode head = null;
public void endInsert(int value) {
//要插入的新节点
ListNode newListNode = new ListNode(value);
//判断头结点是否为空,空就通过值传递把新节点传给头节点,直接return不再走下面的流程
if (head == null) {
head = newListNode;
return;
}
//定义游标temp
ListNode temp = head;
//通过游标判断此节点的next指针域是否为空,不是就指向下一个节点
while(temp.next != null) {
temp = temp.next;
}
//此时指向最后一个节点,让它的next指针域指向新节点
temp.next = newListNode;
}
}
4.获取单链表长度
代码如下:
public class LinkList {
public int getNodeLength(ListNode head) {
if (head == null) {
return 0;
}
ListNode temp = head;
int length = 0;
while(temp != null) {
length ++;
temp = temp.next;
}
return length;
}
}
————————————————
参考:https://blog.****.net/m566666/article/details/121711252
上一篇: 成功的第二步,管理他人
推荐阅读
-
详解单链表的头部插入和尾部添加方法
-
如何在单链表中实现头部添加和尾部添加的操作
-
创建链表:表头和表尾插入方法
-
py 单链表头插入和表尾插入方法的实现(附代码测试)
-
Java 链表的头部插入和尾部插入
-
链表的数据结构和算法 3 - 单向链表的插入、删除、修改和查找(Java 版)
-
使用头部插值和尾部插值方法创建、删除和遍历单个链表
-
单链表创建--头部插入法创建带头部节点的单链表,超详细--头部插入法和尾部插入法,这里记录头部插入法创建带头部节点的单链表的具体过程: 以 C 语言为例。 1)首先使用 typedef 关键字定义节点数据类型 1 typedef struct LNode{ 2 int var; // 以整数数据为例 3 struct LNode* next; // 需要定义一个 LNode 结构指针,即指向后继节点的节点指针 4 }LNode, *LinkList. 第 4 行中的 LNode 和 *LinkList 是可选的,但如果有了它们,以后再定义节点和指针变量会更方便,而且不必在 LNode 前面添加 struct 关键字,而是可以直接这样定义变量。 LNode l1, l2; // 定义节点变量。 LinkList p1, p2; // 定义指针变量。 与上述 typedef 关键字定义的单一链表数据类型的方法相同: struct LNode{ struct LNode* next; //定义指针变量 struct LNode* next; } } 如果使用这种方法定义链表节点的类型,则在定义节点变量和指针变量时,必须在 LNode 前面加上 struct 关键字,即 struct LNode l1, l2; // 定义节点变量 struct LNode *p1, *p2; //define pointer variables. 这两种方法的效果是一样的,都是定义一个包含整数变量数据字段和后续指针字段的单一链表节点类型。 (2)通过表头插入的函数构建一个链表,并返回 LinkList 类型表头指针变量 L。 算法的基本思想:一个有头节点的单链表有两类节点,头节点和元素节点,头节点通常不存储数据,用 L 表示,元素节点存储数据,用 s 表示。 2.1 定义头节点指针变量 L 和元素节点 s
-
头部插入和尾部插入摘要(活动影像版)
-
单个链接表 - 单个链接表的定义和基本操作(头部插入、尾部插入以建立表格、查找、插入、删除等)