使用js实现链表

- 日理万妓 2022-05-08 15:08 129阅读 0赞

>        链表是一种动态的数据结构，不同于数组的是，链表分配内存空间的灵活性，它不会像数组一样被分配一块连续的内存。当你想在数组的任意位置，插入一个新值的时候，必须对数组中的各个元素进行相应的位置移动才能达到目标，开销显然是很大的。然而链表的灵活性在于它的每个元素节点分为两部分，一部分是存储元素本身，另一部分是指向下一个节点元素的引用，也可以称为指针，当你要插入数据时，把上一个节点的向下指针指向新数据节点，新数据节点的向下指针指向原有数据。但是链表不像数组那样可以直接通过索引立刻定位，只能通过遍历。

*  单链表

function List() {       
        this.head = new Node("head");
        this.find = find;
        this.insert = insert;
        this.remove = remove;
        this.getAll= getAll;
        this.findPrevious = findPrevious;        
    }
    
    function Node(element) {
        this.element = element;
        this.next = null;
    }
    
    function find(item) {
        var currNode = this.head;
        while(currNode.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    }
    
    function insert(newElement,item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        if(current == null) 
            return console.log("can't find the item");
        newNode.next = current.next;
        current.next = newNode;
    }
    
    function remove(item) {
        var prevNode = this.findPrevious(item);
        if(prevNode.next != null)
            prevNode.next = prevNode.next.next;
    
    }
    
    function findPrevious(item) {
        var currNode = this.head;
        while(currNode.next != null && currNode.next.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    }
    
    function getAll() {
        var current = this.head;
        while(current.next != null) {
            console.log(current.next.element);
            current = current.next;
        }
    }

*  双向链表

function LList() {           
        this.head = new LNode("head");
        this.findLast = findLast;
        this.insert = insert;
        this.remove = remove;
        this.getAll = getAll;
    }
    
    function LNode(element) {     //双向链表结点
        this.element = element;
        this.next = null;
        this.prev = null;
    }
    
    function insert(newElement.item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        current.next.prev = newNode;
        newNode.prev = current;
        current.next = newNode;
    }
    
    function remove(item) {
        var current = this.find(item);
        if(current.next != null) {
            current.prev.next = current.next;
            current.next.prev = current.prev;
            current.next = null;
            current.prev = null;
        }   
    }
    
    function findLast() {
        var currNode = this.head;
        while(current.next != null) {
            current = current.next;
        }
        return current;
    }
    
    function dispReverse() {            //反序显示双向链表的元素
        var currNode = this.findLast();
        while(currNode.prev != null) {
            console.log(currNode.element);
            currNode = currNode.prev;
        }
    }

*  循环链表

function CList() {                 
        this.head = new Node("head");
        this.head.next = this.head;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

相关使用 scala 实现双向链表

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在

港控/mmm°/ 2023年06月23日 14:24/ 0 赞/ 38 阅读

相关 148. 排序链表（JS实现）

1 题目 > 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 > 示例 1: > 输入: 4->2->1->3 > 输出: 1->

向右看齐/ 2023年03月04日 08:18/ 0 赞/ 18 阅读

相关 143. 重排链表（JS实现）

1 题目 > 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， > 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… > 你不能只是单纯

╰+哭是因爲堅強的太久メ/ 2023年03月04日 08:16/ 0 赞/ 38 阅读

相关 142. 环形链表 II（JS实现）

1 题目 > 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 > 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表

我会带着你远行/ 2023年03月04日 08:16/ 0 赞/ 14 阅读

相关 141. 环形链表（JS实现）

1 题目 > 给定一个链表，判断链表中是否有环。 > 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos

绝地灬酷狼/ 2023年03月04日 08:15/ 0 赞/ 25 阅读

相关 328. 奇偶链表（JS实现）

1 题目 > 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 > 请尝试使用

太过爱你忘了你带给我的痛/ 2022年11月28日 00:42/ 0 赞/ 202 阅读

相关 234. 回文链表（JS实现）

1 题目 > 请判断一个链表是否为回文链表。 > 示例 1: > 输入: 1->2 > 输出: false > 示例 2: > 输入: 1->2->2

比眉伴天荒/ 2022年11月27日 12:29/ 0 赞/ 129 阅读

相关【JS】js链表

[https://juejin.im/post/6844904001557757959][https_juejin.im_post_6844904001557757959]

红太狼/ 2022年11月20日 08:03/ 0 赞/ 191 阅读

相关使用js实现链表

> 链表是一种动态的数据结构，不同于数组的是，链表分配内存空间的灵活性，它不会像数组一样被分配一块连续的内存。当你想在数组的任意位置，插入一个新值的时候，必须对数

- 日理万妓/ 2022年05月08日 15:08/ 0 赞/ 130 阅读

相关 JS实现单向链表、双向链表、循环链表

[https://cloud.tencent.com/developer/article/1114246][https_cloud.tencent.com_developer_

怼烎@/ 2021年12月23日 16:49/ 0 赞/ 446 阅读