JS数据结构与算法--单向链表

2018/07/13 10:28
阅读数 3

链表结构:链表中每个元素由一个存储元素本身的节点和一个指向下一元素的引用组成。如下所示(手画的,比较丑,懒得用工具画了,嘻嘻)

1.append方法,向链表末尾插入一个节点

2.insert(position,element),向指定位置插入一个节点

3.removeAt(position)移除某个位置上的节点

具体实现代码如下:

"use strict";

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}
/**
 * 单向链表
 */
class LinkedList {
    constructor() {
        this.length = 0;
        this.head = null;
    }

    append(element) {
        let node = new Node(element),
            current;
        if (this.getHead() === null) {  //判断链表是否为空
            this.head = node;
        }
        else {
            current = this.getHead();
            while (current.next) { //最后一项的next=null
                current = current.next;
            }
            current.next = node;
        }

        this.length++;
    }


    insert(position, element) {
        if (position >= 0 && position <= this.size()) {   //检查边界
            let node = new Node(element),
                current = this.head,
                index = 0,
                previous;
            if (position === 0) {   //插入第一项
                this.head = node;
                node.next = current;
            }
            else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;

                }
                node.next = current;
                previous.next = node;
            }

            this.length++;
            return true;
        }
        else {
            return false;
        }
    }

    removeAt(position) {
        if (position >= 0 && position <= this.length) {
            let current = this.head,
                index = 0,
                previous;
            if (position === 0) {
                this.head = current.next;
            }
            else {
                while (index++ < position) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.length--;
            return current.element;
        }
        else {
            return null;
        }
    }

    indexOf(element) {
        let current = this.getHead(), index=0;
        while (current) {
            if(current.element===element){
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }

    remove(element) {
        let position = this.indexOf(element);
        return this.removeAt(position);
    }

    getHead() {
        return this.head;
    }

    isEmpty() {
        return this.length === 0;
    }

    size() {
        return this.length;
    }

    toString() {

        let current = this.getHead(),
            string = '';

        while (current) {
            string += current.element + (current.next ? ', ' : '');
            current = current.next;
        }
        return string;

    }

    print() {
        console.log(this.toString());
    }
}

  

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部