首页 > 其他分享 >单向链表

单向链表

时间：2022-10-27 16:12:03浏览次数：38  
标签：current 单向 list next 链表 position data

单向链表

链表的简介

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有的语言称为指针或连接）组成。类似于火车头，火车头会连接一个节点，车厢（节点）载着乘客（数据），通过节点连接另一节车厢。

image-20221026145648527

链表的优势：

  • 链表中的元素在内存中不必是连续的空间，可以充分利用计算机的内存，实现灵活的内存动态管理
  • 链表不必在创建时就确定大小，并且大小可以无限地延伸下去
  • 链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多

链表的缺点：

  • 链表访问任何一个位置的元素时，都需要从头开始访问（无法跳过第一个元素访问任何一个元素）
  • 无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素
  • 虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的

链表中的常见操作：

  • append（data）：向链表尾部添加一个新的项
  • insert（position，data）：向链表的特定位置插入一个新的项，返回值为Boolean
  • get（position）：获取对应位置的元素
  • indexOf（data）：返回元素在链表中的索引。如果链表中没有该元素就返回-1
  • update（position，data）：修改某个位置的元素，返回值为Boolean
  • removeAt（position）：从链表的特定位置移除一项，返回值为被移除的数据
  • remove（data）：从链表中移除一项，返回值为Boolean
  • isEmpty（）：如果链表中不包含任何元素，返回trun，如果链表长度大于0则返回false
  • size（）：返回链表包含的元素个数，与数组的length属性类似
  • toString（）：由于链表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值

封装单向链表

1.创建类

// 节点类
class Node {
    constructor(data) {
        // 数据
        this.data = data
        // 指向下一个节点
        this.next = null
    }
}
// 封装链表类
class LinkedList {
    constructor() {
        // 链表的头
        this.head = null
        // 记录链表的长度
        this.length = 0
    }
}

2.append(data)

向链表尾部追加数据可能有两种情况：

  • 链表本身为空，添加的数据是唯一节点，需要把head指向节点

  • 链表不为空，需要在链表最后面追加节点，并让链表最后一个节点指向此节点

    代码实现

append(data) {
    // 1.创建新的节点
    let newNode = new Node(data)
    // 2.判断添加的是否是第一个节点
    if (!this.length) {

        this.head = newNode
    } else {
        // 2.2不是第一个节点
        // 查出最后一个节点
        let current = this.head
        while (current.next) {
            current = current.next
        }
        // 在最后的节点的next上添加节点
        current.next = newNode
    }
    // 节点长度加一
    this.length += 1
}

测试

// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
console.log(list);

image-20221026161940743

3.insert（position，data）

image-20221027103825934

插入一条数据有三种可能发生情况

  1. position大于链表长度或者为负数
    • return false
  2. position = 0
    • 插在head后面
    • image-20221027103836935
  3. position > 0
    • previous和current分别指向需要插入位置前一个节点和要插入的节点
    • newNode的next指向current ，previous的next指向newNode
    • image-20221027103921335
// 指定位置插入数据
inster(position, data) {
    // 1.对position进行越界判断
    if (position < 0 || position > this.length) return false

    // 2.根据data创建Node
    let newNode = new Node(data)

    // 3.插入newNode
    // 插入数据有两种情况
    // 第一种是position是0，插在head后
    if (position === 0) {
        newNode.next = this.head
        this.head = newNode
    } else {
        // 第二种情况是position>0
        let index = 0
        let current = this.head
        let preNode = null // 存放要插入位置的上一个
        while (current) {
            preNode = current
            current = current.next
            index++
            if (index === position) {
                newNode.next = current
                preNode.next = newNode
                break
            }
        }
    }
    // 4.length+1
    this.length += 1
    return true
}

测试

// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
list.inster(2, 'test')
console.log(list);

image-20221027140307277

4.get（position）

// 获取对应位置的元素
get(position) {
    // 1.越界判断
    if(position < 0 || position > this.length - 1) return null
    // 2.根据position获取对应的数据
    let current = this.head
    let index = 0
    while (current) {
        if (index === position) {
            return current.data
        }
        current = current.next
        index++
    }
}

测试

// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
console.log(list.get(1)); // 结果：jack-2

5.indexOf（data）

// 返回数据在链表中的索引，如果没有，则返回-1
indexOf(data) {
    // 定义变量
    let index = 0
    let current = this.head
    // 开始查找
    while (current) {
        // 每次循环判断data是否相等
        if (data === current.data) {
            return index
        }
        // 不相等就current等于本身的next，准备下次循环使用
        current = current.next
        // 没循环一次 下标要+1
        index += 1
    }
    // 循环完毕，没有找到相等的data
    return -1
}

测试

// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
list.indexOf('tom-1')
console.log(list.indexOf(1)); // 结果：-1
console.log(list.indexOf('tom-1')); // 结果： 0
console.log(list.indexOf('city-3')); // 结果： 2

6.update（position，data）

// 修改某个位置的元素
update(position, newData) {
    // 1.越界判断
    if (position < 0 || position > this.length - 1) return false
    // 2.根据position坐标获取要修改的数据
    let current = this.head
    let index = 0
    while (current) {
        // 2.1坐标相同，修改数据
        if (index === position) {
            current.data = newData
            return true
        }
        // 2.2不相同，为下次循环做数据准备
        current = current.next
        index += 1
    }
}

测试

// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
console.log(list);

image-20221027145713088

7.removeAt（position）

// 删除链表中指定位置的数据
removeAt(position) {
    // 1.越界判断
    if (position < 0 || position > this.length - 1) return null
    // 2.声明需要的变量
    let index = 0
    let current = this.head
    let preNode = null // 当前节点的上一个
    // 3.有两种情况，一种是position等于0,
    if (position === 0) {
        current = this.head
        this.head = this.head.next
    } else {
        // 第二种情况是position不等于0
        while (current) {
            // 坐标相同
            if (index === position) {
                // 上一个坐标的next等于当前坐标的next，即跳过了当前节点的data
                preNode.next = current.next
                break
            }
            // 记录当前节点的上一个
            preNode = current
            current = current.next
            index += 1
        }
    }
    // 4.链表长度更新
    this.length -= 1
    return current.data
}

测试

// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
console.log(list);

image-20221027153714807

8.remove（data）

remove(data) {
    // 1.通过数据获取坐标，使用封装过的indexOf方法
    let index = this.indexOf(data)
    // 2.通过坐标删除链表中的数据，使用已经封装过的removeAt方法
    return !!this.removeAt(index) // !! 转换成布尔型
}

测试

// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
console.log(list.remove('jack-2'));

image-20221027155537253

9.sEmpty（）

isEmpty() {
    return !!this.length
}

10.size（）

size() {
    return this.length
}

11.toString（）

实现流程：

  • 主要是获取每一个元素
  • 从head开始，遍历每一个节点，取出其中的data，拼接成字符串
  • 最终将字符串返回

​ 代码实现：

// 转换成字符串
toString() {
    // 1.定义变量
    let current = this.head
    let res = ''
    // 2.循环每一个节点
    while (current) {
        res += current.data + ' '
        current = current.next
    }
    return res
}
// 测试
const list = new LinkedList()
list.append('tom-1')
list.append('jack-2')
list.append('city-3')
console.log(list.toString()); // tom-1 jack-2 city-3

整体代码

// 节点类
class Node {
    constructor(data) {
        // 数据
        this.data = data
        // 指向下一个节点
        this.next = null
    }
}
// 封装链表类
class LinkedList {
    constructor() {
        // 链表的头
        this.head = null
        // 记录链表的长度
        this.length = 0
    }
    // 末尾添加一个节点
    append(data) {
        // 1.创建新的节点
        let newNode = new Node(data)
        // 2.判断添加的是否是第一个节点
        if (!this.length) {
            this.head = newNode
        } else {
            // 2.2不是第一个节点
            // 查出最后一个节点
            let current = this.head
            while (current.next) {
                current = current.next
            }
            // 在最后的节点的next上添加节点
            current.next = newNode
        }
        // 节点长度加一
        this.length += 1
    }
    // 转换成字符串
    toString() {
        // 1.定义变量
        let current = this.head
        let res = ''
        // 2.循环每一个节点
        while (current) {
            res += current.data + ' '
            current = current.next
        }
        return res
    }
    // 指定位置插入数据
    inster(position, data) {
        // 1.对position进行越界判断
        if (position < 0 || position > this.length) return false

        // 2.根据data创建Node
        let newNode = new Node(data)

        // 3.插入newNode
        // 插入数据有两种情况
        // 第一种是position是0，插在head后
        if (position === 0) {
            newNode.next = this.head
            this.head = newNode
        } else {
            // 第二种情况是position>0
            let index = 0
            let current = this.head
            let preNode = null // 存放要插入位置的上一个
            while (current) {
                preNode = current
                current = current.next
                index++
                if (index === position) {
                    newNode.next = current
                    preNode.next = newNode
                    break
                }
            }
        }
        // 4.length+1
        this.length += 1
        return true
    }
    // 获取对应位置的元素
    get(position) {
        // 1.越界判断
        if (position < 0 || position > this.length - 1) return null
        // 2.根据position获取对应的数据
        let current = this.head
        let index = 0
        while (current) {
            if (index === position) {
                return current.data
            }
            current = current.next
            index++
        }
    }
    // 返回数据在链表中的索引，如果没有，则返回-1
    indexOf(data) {
        // 定义变量
        let index = 0
        let current = this.head
        // 开始查找
        while (current) {
            // 每次循环判断data是否相等
            if (data === current.data) {
                return index
            }
            // 不相等就current等于本身的next，准备下次循环使用
            current = current.next
            // 没循环一次 下标要+1
            index += 1
        }
        // 循环完毕，没有找到相等的data
        return -1
    }
    // 修改某个位置的元素
    update(position, newData) {
        // 1.越界判断
        if (position < 0 || position > this.length - 1) return false
        // 2.根据position坐标获取要修改的数据
        let current = this.head
        let index = 0
        while (current) {
            // 2.1坐标相同，修改数据
            if (index === position) {
                current.data = newData
                return true
            }
            // 2.2不相同，为下次循环做数据准备
            current = current.next
            index += 1
        }
    }
    // 删除链表中指定位置的数据
    removeAt(position) {
        // 1.越界判断
        if (position < 0 || position > this.length - 1) return null
        // 2.声明需要的变量
        let index = 0
        let current = this.head
        let preNode = null // 当前节点的上一个
        // 3.有两种情况，一种是position等于0,
        if (position === 0) {
            current = this.head
            this.head = this.head.next
        } else {
            // 第二种情况是position不等于0
            while (current) {
                // 坐标相同
                if (index === position) {
                    // 上一个坐标的next等于当前坐标的next，即跳过了当前节点的data
                    preNode.next = current.next
                    break
                }
                // 记录当前节点的上一个
                preNode = current
                current = current.next
                index += 1
            }
        }
        // 4.链表长度更新
        this.length -= 1
        return current.data
    }

    // 从链表中移除指定值
    remove(data) {
        // 1.通过数据获取坐标，使用封装过的indexOf方法
        let index = this.indexOf(data)
        // 2.通过坐标删除链表中的数据，使用已经封装过的removeAt方法
        return !!this.removeAt(index)

    }
    // 判断链表有没有数据
    isEmpty() {
        return !!this.length
    }
    // 返回链表的长度
    size() {
        return this.length
    }
}

标签：current,单向,list,next,链表,position,data
From： https://www.cnblogs.com/codehaoran/p/16832598.html

相关文章

  • leetcode 234. 回文链表 js 实现
    给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。 示例1：输入：head=[1,2,2,1]输出：true示例2：输入：head=[1,2]输出......
  • 数据结构 玩转数据结构 4-1 什么是链表
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13429 1重点关注1.1什么是链表数据存在节点中的一种线性数据结构  1.2......
  • leetcode 206. 反转链表 js实现
    给你单链表的头节点head，请你反转链表，并返回反转后的链表。 示例1：输入：head=[1,2,3,4,5]输出：[5,4,3,2,1]示例2：输入：head=[1,2]输出：[2,1]示例3：输入：head=[]输出......
  • 力扣-92-反转链表Ⅱ
    其实对链表的考察就是考察指针，不喜欢Java写算法题的一大原因就是Java没有指针区间反转链表，相对于整体反转链表而言回忆一下链表的整体反转，大概是两种做法递归，从后往前......
  • 链表——环形链表
    classSolution{public:ListNode*detectCycle(ListNode*head){ListNode*fast=head;ListNode*slow=head;while(fast!=NULL&......
  • 【数据结构-链表】链表的基本操作
    目录1单向链表1.1有头结点的单向链表1.1.1数据结构定义1.1.2初始化建立链表1.1.3按序号查找结点1.1.4按值查找结点1.1.5插入操作1.1.6删除操作1.2无头结点的单向......
  • 链表——删除链表倒数第n个节点
    classSolution{public: ListNode*deleteback(ListNode*head,intn) { ListNode*dummyHead=newListNode(0); dummyHead->next=head; ListNode*fast......
  • 单链表翻转
    使用语言：c++。#include<iostream>usingnamespacestd;//链表structListNode{intval;ListNode*next;ListNode(intval,ListNode*next=NULL):val(val),......
  • 链表--链表平均分割成几个子链表的方案
    725. SplitLinkedListinPartsMedium36682FavoriteShareGivena(singly)linkedlistwithheadnode ​​root​​​,writeafunctiontosplitthelinkedlisti......
  • 链表——两两交换链表中的节点
    #include<iostream>usingnamespacestd;structListNode{ intval; ListNode*next; ListNode(intval):val(val),next(NULL){};};//根据数组创建链表Lis......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99