手写链表
程序员文章站
2022-05-06 08:49:48
...
一、链表结构
- 每个节点结构是由数据域和指针域组成,数据域是存放数据的,而指针域存放下一结点的地址。
- 但是不可能只有一个节点呀,这时候就使用 Class 来声明一个类,为类添加两个属性,一个属性是存放数据的属性data,另一个属性是存放指向下一个结点的指针属性next。这样就可以创造出多个结点实例。
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
二、插入删除
- 插入到单链表的头部
- 插入到中间
- 插入到尾部
- 删除头部节点
- 删除中间节点
- 删除尾部节点
三、边界条件
-
输入边界:
先考虑用户输入的参数,比如传入一个链表,我们首先要判断链表是否为空,如果为空我们就不能让它执行下边的程序。再比如插入一个结点到指定结点的后边,那么你也要判断输入的结点是否为空,而且还要判断该结点是否存在该链表中。对于这些输入值的判断,就叫做输入边界。 -
特殊边界:
考虑到一些特殊情况,比如插入数据,我们插入数据一般考虑到插入尾部,但要是插入到头部,插入尾部的代码并不适用于插入到头部,所以呢需要考虑这种情况,删除节点也是同样要考虑这种情况。其实特殊边界最主要考虑到一些逻辑上的特殊情况。
四、示例
例:在链表中间增加和删除节点
1. 定义节点:
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
2. 增加节点:
①保存临时地址(4结点的地址),需要进行遍历查找到3结点,也就是下列代码的currentNode 结点。
//先查找该元素
let currentNode = this.findByValue(element);
// 保存 3 结点的下一结点地址(4 结点的地址)
let pre = currentNode.next
②创建新结点,将新结点(5结点)的指针指向下一结点指针(4结点地址,已经在上一步骤保存下来了)
let newNode = new Node(value);
newNode.next = pre;
③将3 的结点地址指向新结点(5结点)
currentNode.next = newNode;
3. 删除节点:
①断开3结点的指针(断开3结点相当于让2结点直接指向4结点)
let currentNode = this.head;
// 用来记录 3 结点的前一结点
let preNode = null;
// 遍历查找 3 结点
while(currentNode !== null && currentNode.data !== value){
// 3 结点的前一结点
preNode = currentNode;
// 3 结点
currentNode = currentNode.next;
}
②让结点2的指针指向4结点,完成删除。
preNode.next = currentNode.next;
五、代码实现
/**
* 功能:单链表的插入、删除、查找
* 【插入】:插入到指定元素后方
* 1、查找该元素是否存在?
* 2、没有找到返回 -1
* 3、找到进行创建结点并插入链表。
*
* 【查找】:按值查找/按索引查找
* 1、判断当前结点是否等于null,且是否等于给定值?
* 2、判断是否可以找到该值?
* 3、没有找到返回 -1;
* 4、找到该值返回结点;
*
* 【删除】:按值删除
* 1、判断是否找到该值?
* 2、找到记录前结点,进行删除;
* 3、找不到直接返回-1;
*/
//定义结点
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
//定义链表
class LinkList{
constructor(){
//初始化头结点
this.head = new Node('head');
}
//根据 value 查找结点
findByValue = (value) =>{
let currentNode = this.head;
while(currentNode !== null && currentNode.data !== value){
currentNode = currentNode.next;
}
//判断该结点是否找到
console.log(currentNode)
return currentNode === null ? -1 : currentNode;
}
//根据 index 查找结点
findByIndex = (index) =>{
let pos = 0;
let currentNode = this.head;
while(currentNode !== null && pos !== index){
currentNode = currentNode.next;
pos++;
}
//判断是否找到该索引
console.log(currentNode)
return currentNode === null ? -1 : currentNode;
}
//插入元素(指定元素向后插入)
insert = (value,element) =>{
//先查找该元素
let currentNode = this.findByValue(element);
//如果没有找到
if(currentNode == -1){
console.log("未找到插入位置!")
return;
}
let newNode = new Node(value);
newNode.next = currentNode.next;
currentNode.next = newNode;
}
//根据值删除结点
delete = (value) =>{
let currentNode = this.head;
let preNode = null;
while(currentNode !== null && currentNode.data !== value){
preNode = currentNode;
currentNode = currentNode.next;
}
if(currentNode == null) return -1;
preNode.next = currentNode.next;
}
//遍历所有结点
print = () =>{
let currentNode = this.head
//如果结点不为空
while(currentNode !== null){
console.log(currentNode.data)
currentNode = currentNode.next;
}
}
}