前端算法：数据结构、双向、闭环、有序链表

terry 2年前 (2023-09-27) 阅读数 71 #数据结构与算法

链表

链表是一种什么样的结构？链表是一种可以链接数据的结构。每个元素都有一个指向下一个元素的指针（不是最后一个简单的链表），就像现实世界中的一列火车是一个接一个地链起来的；链表根据其指针可分为：单向链表、双向链表、循环链表；

链表首先会有一个表头，也就是初始指针，然后每个元素称为节点；每个元素称为一个节点。每个节点都有一个指针（next）指向下一个节点，直到链表末尾该指针将指向undefined；

链表实现

1、节点

节点的创建和定义；每个节点都会有一个属性保存自己数据的一个属性（元素），然后有一个指针（next）

export class Node {
    constructor(element, next = null) {
        this.element = element;
        this.next = next;
    }
}

2、链表api

getElementAt(position): 获取某个位置的元素

append(element):将元素添加到链表末尾

removeAt(idx):删除元素

插入元素='be',di,插入0(元素)') : 将元素添加到指定位置

insertAfter(element,position): 在指定位置后添加元素

size(): 列表长度长度 remove(): 删除链表末尾元素

removeAll(): 删除整个链表

为空检查是否为空():3.在链表附件末尾添加一个元素；

    append(element) {
        const node = new Node(element);
        let current = this.head;
        if(current == null) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next !=  null) {
                current = current.next;
            }
            current.next = node
        }
        this.count++;
        return element;
    }

4。插入元件

    insert(element, position = 0, dir = 'before') {
        if (element === undefined) {
             throw Error('缺少需要插入的元素');
             return;
        }
        if (position >= this.count) {
            return this.append(element);
        }
        const node = new Node(element);
        const targetNode = dir === 'before' ? this.getElementAt(position - 1) : this.getElementAt(position);
        if (!targetNode) {
            let prev = this.head;
            this.head = node;
            node.next = prev;
        } else {
            let next;
            next = targetNode.next
            targetNode.next = node;
            node.next = next;
        }
        this.count++;
        return element;
    }

5。删除元素

removeAt(idx) {
        if (idx >= 0 && idx < this.count) {
            let current = this.head;
            if (idx === 0) {
                this.head = current.next;
                current.next = null;
            } else {
                let prev = this.getElementAt(idx - 1);
                current = prev.next;
                prev.next = current.next;
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }

6。双向链表

单向链表的元素都指向一个方向，只能在一个方向递归查找，而双向链表不仅有指向下一个元素的指针，还指向上一个元素。指标;

import LinkedList from "./LinkedList";
import {defaultEquals} from "../util";
import { DoubleNode } from "./DoubleNode";

export default class DoubleLinkedList extends LinkedList{
    constructor(equalIsFn = defaultEquals){
        super(equalIsFn);
        this.tail = null;// 队列尾部
    }
    getElementAt(position) {
        if(position >= 0 && position <= this.count) {
            if (position > this.count/2) {
                let cur = this.tail;
                for (let i = this.count - 1; i > position; i--){
                    cur = cur.prev;
                }
                return cur;
            } else {
                return super.getElementAt(position)
            }
        }
        return undefined;
    }
    removeAll() {
        super.removeAll();
        this.tail = null;
    }
    removeAt(position) {
        if (position >= 0 && position < this.count) {
            let cur = this.getElementAt(position);
            if(position === 0) {
                this.head = cur.next;
                cur.next = null;
                this.prev = null;
            } else if (position === this.count - 1) {
                this.tail = cur.prev;
                this.tail.next = null;
                cur.prev = null;
            } else {
                let prev = cur.prev;
                let next = cur.next;
                prev.next = next;
                next.prev = prev;
                cur.prev = null;
                cur.next = null;
            }
            this.count--;
            return cur.element;
        }
        return undefined;
    }
}

向队列末尾插入元素（追加）

向双向链表插入元素与单向链接类似，只不过双向链接不仅必须链接其子级，还必须链接其上一级;

    append(element) {
        const node = new DoubleNode(element);
        if (!this.tail) {
            this.head = node;
            this.tail = node;
        } else {
            let cur = this.tail;
            cur.next = node;
            node.prev = cur;
            this.tail = node;
        }
        this.count++;
        return element;
    }

中间某处在每个位置插入一个元素

insert(element, position = 0, dir = 'before'){
        if (element === undefined) {
            throw Error('缺少需要插入的元素');
            return;
        }
        if (position >= this.count) {
            return this.append(element);
        }
        const node = new DoubleNode(element);
        let cur;
        const targetNode = dir === 'before' ? this.getElementAt(position - 1) : this.getElementAt(position);
        if (!targetNode) {
            cur = this.head;
            node.next = cur;
            cur.prev = node;
            this.head = node;
        } else {
            let next;
            next = targetNode.next
            targetNode.next = node;
            node.prev = targetNode;
            node.next = next;
            next.prev = node;
        }
        this.count++;
        return element;
    }