ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Generic Data Structure: Doubly Linked List

TypeScript

Goal -- WPM

Ready
Exercise Algorithm Area
1class DoublyLinkedListNode<T> {

2value: T;

3next: DoublyLinkedListNode<T> | null = null;

4prev: DoublyLinkedListNode<T> | null = null;

5

6constructor(value: T) {

7this.value = value;

8}

9}

10

11class DoublyLinkedList<T> {

12private head: DoublyLinkedListNode<T> | null = null;

13private tail: DoublyLinkedListNode<T> | null = null;

14private count: number = 0;

15

16/**

17* Adds a new node with the given value to the beginning of the list.

18*/

19addFirst(value: T): void {

20const newNode = new DoublyLinkedListNode(value);

21if (!this.head) {

22// List is empty

23this.head = newNode;

24this.tail = newNode;

25} else {

26// List has existing nodes

27newNode.next = this.head;

28this.head.prev = newNode;

29this.head = newNode;

30}

31this.count++;

32}

33

34/**

35* Adds a new node with the given value to the end of the list.

36*/

37addLast(value: T): void {

38const newNode = new DoublyLinkedListNode(value);

39if (!this.tail) {

40// List is empty

41this.head = newNode;

42this.tail = newNode;

43} else {

44// List has existing nodes

45this.tail.next = newNode;

46newNode.prev = this.tail;

47this.tail = newNode;

48}

49this.count++;

50}

51

52/**

53* Removes and returns the first node's value from the list.

54* Returns undefined if the list is empty.

55*/

56removeFirst(): T | undefined {

57if (!this.head) {

58return undefined; // List is empty

59}

60

61const removedValue = this.head.value;

62if (this.head === this.tail) {

63// Only one node in the list

64this.head = null;

65this.tail = null;

66} else {

67// More than one node

68this.head = this.head.next;

69this.head!.prev = null;

70}

71this.count--;

72return removedValue;

73}

74

75/**

76* Removes and returns the last node's value from the list.

77* Returns undefined if the list is empty.

78*/

79removeLast(): T | undefined {

80if (!this.tail) {

81return undefined; // List is empty

82}

83

84const removedValue = this.tail.value;

85if (this.head === this.tail) {

86// Only one node in the list

87this.head = null;

88this.tail = null;

89} else {

90// More than one node

91this.tail = this.tail.prev;

92this.tail!.next = null;

93}

94this.count--;

95return removedValue;

96}

97

98/**

99* Converts the list to an array.

100*/

101toArray(): T[] {

102const result: T[] = [];

103let currentNode = this.head;

104while (currentNode) {

105result.push(currentNode.value);

106currentNode = currentNode.next;

107}

108return result;

109}

110

111/**

112* Returns the number of nodes in the list.

113*/

114size(): number {

115return this.count;

116}

117}
Algorithm description viewbox

Generic Data Structure: Doubly Linked List

Algorithm description:

This implementation provides a generic `DoublyLinkedList` data structure. It allows elements of any type `T` to be added or removed from both the beginning and end of the list. Each node in the list maintains references to both the next and previous nodes, enabling efficient traversal in both directions. Doubly linked lists are used in scenarios requiring frequent insertions/deletions at arbitrary positions and for implementing structures like deques or undo/redo functionalities.

Algorithm explanation:

The `DoublyLinkedList` is composed of `DoublyLinkedListNode` objects, each holding a `value` and pointers to the `next` and `prev` nodes. The list itself maintains pointers to the `head` and `tail` nodes, and a `count` of elements. `addFirst` creates a new node, setting its `next` to the current `head` and updating `head` and `head.prev`. `addLast` similarly updates `tail` and `tail.next`. Both methods handle the edge case of an empty list by setting both `head` and `tail` to the new node. `removeFirst` and `removeLast` handle the removal of the first/last node, correctly updating `head`/`tail` and their respective `prev`/`next` pointers, including the case where the list becomes empty. `toArray` iterates from `head` to `tail`, collecting values. The time complexity for `addFirst`, `addLast`, `removeFirst`, `removeLast`, and `size` is O(1). `toArray` has a time complexity of O(n), where n is the number of elements. Space complexity is O(n) for storing the list elements.

Pseudocode:

class DoublyLinkedListNode<T>:
  value: T
  next: Node | null
  prev: Node | null

class DoublyLinkedList<T>:
  head: Node | null
  tail: Node | null
  count: integer

  method addFirst(value):
    create newNode with value
    if list is empty:
      head = newNode, tail = newNode
    else:
      newNode.next = head
      head.prev = newNode
      head = newNode
    increment count

  method addLast(value):
    create newNode with value
    if list is empty:
      head = newNode, tail = newNode
    else:
      tail.next = newNode
      newNode.prev = tail
      tail = newNode
    increment count

  method removeFirst() returns T or undefined:
    if list is empty: return undefined
    value = head.value
    if head == tail: head = null, tail = null
    else: head = head.next, head.prev = null
    decrement count
    return value

  method removeLast() returns T or undefined:
    if list is empty: return undefined
    value = tail.value
    if head == tail: head = null, tail = null
    else: tail = tail.prev, tail.next = null
    decrement count
    return value

  method toArray() returns array:
    result = empty array
    current = head
    while current is not null:
      add current.value to result
      current = current.next
    return result

  method size() returns integer:
    return count