[TS] Implement a doubly linked list in TypeScript
Listtypescript in TS Linked Implement
2023-09-14 08:59:17 时间
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([]); });
相关文章
- List集合中的对象根据属性排序
- [Typescript] Convert a js project to typescript
- [Typescript] Making TypeScript Stick - 5 - Extends
- [React Typescript 2022] Use TypeScript to Type a React Class Component
- [Typescript] Narrow the unknown Type with TypeScript's Assertion Functions
- [Typescript] Use the Nullish Coalescing Operator in TypeScript (isNil)
- [Typescript] Use the Optional Chaining Operator in TypeScript
- [Typescript Kaop-ts] Use AOP in Vue Components with TypeScript and Kaop-ts
- [TypeScript] Typescript Interfaces vs Aliases Union & Intersection Types
- [Typescript] Convert a js project to typescript
- [React Typescript 2022] Type a Radio Button Component in React using TypeScript
- [Typescript] Make your optional fields required in TypeScript
- [Typescript Kaop-ts] Use AOP in Vue Components with TypeScript and Kaop-ts
- [TypeScript] Typescript Interfaces vs Aliases Union & Intersection Types
- click group list in left launchpad
- Java8——Stream流操作List排序_List集合中每个对象元素按时间顺序排序
- List<?> list= new ArrayList<?>接口引用指向实现类的对象.