[TS] Implement a doubly linked list in TypeScript
Listtypescript in TS Linked Implement
2023-09-14 09:00:51 时间
In a doubly linked list each node in the list stores the contents of the node and a pointer or reference to the next and the previous nodes in the list. It is one of the simplest way to store a collection of items.
In this lesson we cover how to create a doubly linked list data structure and how to use its strengths to implement an O(1) FIFO queue + O(1) LIFO stack. We also demonstrate why one would use it over a singly linked list. We also cover how to approach authoring such data structures.
The reason for use double linked list is that we can do LIFO opreation in O(1), in Single linked List, it requires O(n), because you need to go thought from the head, in order to know what will be the next tail item for new linked list.
/** * Linked list node */ export interface DoublyLinkedListNode<T> { value: T next?: DoublyLinkedListNode<T> prev?: DoublyLinkedListNode<T> } /** * Linked list for items of type T */ export class DoublyLinkedList<T> { public head?: DoublyLinkedListNode<T> = undefined; public tail?: DoublyLinkedListNode<T> = undefined; /** * Adds an item in O(1) **/ add(value: T) { const node: DoublyLinkedListNode<T> = { value, next: undefined, prev: undefined, } if (!this.head) { this.head = node; } if (this.tail) { this.tail.next = node; node.prev = this.tail; } this.tail = node; } /** * FIFO removal in O(1) */ dequeue(): T | undefined { if (this.head) { const value = this.head.value; this.head = this.head.next; if (!this.head) { this.tail = undefined; } else { this.head.prev = undefined; } return value; } } /** * LIFO removal in O(1) */ pop(): T | undefined { if (this.tail) { const value = this.tail.value; this.tail = this.tail.prev; if (!this.tail) { this.head = undefined; } else { this.tail.next = undefined; } return value; } } /** * Returns an iterator over the values */ *values() { let current = this.head; while (current) { yield current.value; current = current.next; } } }
import { DoublyLinkedList } from './doublyLinkedList'; test('basic', () => { const list = new DoublyLinkedList<number>(); list.add(1); list.add(10); list.add(5); expect(Array.from(list.values())).toMatchObject([1, 10, 5]); expect(list.dequeue()).toBe(1); expect(Array.from(list.values())).toMatchObject([10, 5]); expect(list.dequeue()).toBe(10); expect(list.dequeue()).toBe(5); expect(list.dequeue()).toBe(undefined); expect(Array.from(list.values())).toMatchObject([]); list.add(5); list.add(10); list.add(1); expect(Array.from(list.values())).toMatchObject([5, 10, 1]); expect(list.pop()).toBe(1); expect(list.dequeue()).toBe(5); expect(list.pop()).toBe(10); expect(list.pop()).toBe(undefined); expect(list.dequeue()).toBe(undefined); expect(Array.from(list.values())).toMatchObject([]); });
相关文章
- java中数组转列表_Java数组转list
- Doubly Linked List
- Python 合并list 11种方式
- Java- Set 转换成List
- java分页计算公式_java将list分页
- 采用java8 lambda表达式 实现 java list 交集 并集 差集 去重复并集
- Phone List 【 HDU - 1671 】 【 字典树判断是否存在前缀 】
- 【C++】STL 模拟实现之 list
- ORA-31417: column list contains control column string ORACLE 报错 故障修复 远程处理
- ORA-02774: Invalid request list latch time out value ORACLE 报错 故障修复 远程处理
- MySQL Status Mysqlx_stmt_list_notices 数据库状态作用意思及如何正确
- MySQL Status Mysqlx_stmt_list_objects 数据库状态作用意思及如何正确
- 利用Redis实现List元素的排序(redis排序list)
- Redis如何清空List:技巧分享(redis清空list)
- Mastering List Operations in Redis: Tips and Tricks for Optimal Performance(redis操作list)
- 以List形式存储至Redis中(往redis里存list)
- Redis中List实现快速数据查找(redis 选择list)
- Redis自带数据结构List(redis自带list)
- Redis灵活的List储存功能(redis能储存list)
- 集合类List与Dictonary实例练习
- javaCollection之List学习介绍
- 基于C++list中erase与remove函数的使用详解