数据结构—链表 - Githubissues

链表

要储存多个元素，数组可能是最常用的数据结构。但是，在大多数语言中，数组这种结构存在一个缺点，那就是数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。

链表这种结构存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或者链接）组成。

相对于传统的数组，链表的一个好处在于，添加或者移除元素的时候不需要移动其他元素。然而，因为链表是用指针链接的，不同于数组，如果你想访问某个元素，必须从起点开始迭代列表知道找到所需的元素。

创建链表

function LinkedList () {
    let Node = function (element) {
        this.element = element;
        this.next = null;
    }

    let length = 0;
    let head = null;
    // 向列表尾部添加一个新的项
    this.append = function (element) {};
    // 向列表的特定位置插入一个新的项
    this.insert = function (position, element) {};
    // 从列表的特定位置移除一项
    this.removeAt = function (position) {};
    // 从列表中移除一项
    this.remove = function (element) {};
    // 返回元素在列表中的索引。如果列表中没有则返回-1
    this.indexOf = function (element) {};
    // 返回链表是否为空
    this.isEmpty = function () {};
    // 返回链表包含元素的个数
    this.size = function () {};
    // 返回链表的头部
    this.getHead = function () {};
    // 输出每个链表的值
    this.toString = function () {};
    this.print = function () {};
}

然后我们依次实现上述方法

append

this.append = function (element) {
    let node = new Node(element), current;

    if (head === null) {
        head = node;
    } else {
        current = head;
        while (current.next) {
            current = current.next;
        }
        current.next = node;
    }

    length++;
}

removeAt

this.removeAt = function (position) {
    if (position > =1 && position < length) {
        let current = head,
        previous,
        index = 0;

        if (position === 0) {
            head = current.next;
        } else {
            while (index ++ < position) {
                previous = current;
                current = current.next;
            }

            previous.next = current.next;
        }

        length--;

        return current.element;
    } else {
        return null;
    }
}

insert

this.insert = function (position, element) {
    if (position >= 0 && position <= length) {
        let node = new Node(element),
        current = head,
        previous,
        index = 0;

        if (position === 0) {
            head = node;
            node.next = current;
        } else {
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            previous.next = node;
            node.next = current;

            length++;
            return true;
        }

    } else {
        return false;
    }
}

toString

this.toString = function () {
    let current = head,
    string = '';
    while (current) {
        string += current.element + (current.next ? ',' : '');
        current = current.next;
    }
}

indexOf

this.indexOf = function (element) {
    let current = head,
    index = 0;

    while (current) {
        if (element === current.element) {
            return index;
        }
        index ++;
        current = current.next;
    }

    return -1;
}

remove

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

isEmpty

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

size

this.size = function () {
    return size;
}

getHead

this.getHead = function () {
    return head;
}

本次介绍了如何在js中实现一个链表数据结构。大家可以尝试实现一下更复杂的链表结构

双向链表

双向链表和普通链表的区别在于，在链表中一个节点只有链向下一个节点，但是双向链表中，链接是双向的。当前节点即链接下一个元素，也链接上一个元素
循环链表

循环链表是指链表的最后一个元素的下一个元素的指针指向第一个元素

EmberYu / vic-blog

数据结构—链表 #10

链表