Design Front Middle Back Queue LeetCode solution in JavaScript

1
// T.C:
2
// O(1) for init and methods other than pushMiddle(), popMiddle()
3
// O(N) for pushMiddle(), popMiddle()
4
// S.C: O(N) for storage
5

6
// Doubly linked list node
7
function ListNode(val, prev, next) {
8
  this.val = val || 0;
9
  this.prev = prev || null;
10
  this.next = next || null;
11
}
12

13
var FrontMiddleBackQueue = function () {
14
  this.head = null;
15
  this.tail = null;
16
  this.len = 0;
17
};
18

19
/**
20
 * @param {number} val
21
 * @return {void}
22
 */
23
FrontMiddleBackQueue.prototype.pushFront = function (val) {
24
  if (this.len === 0) {
25
    this.head = new ListNode(val);
26
    this.tail = this.head;
27
    this.len += 1;
28
    return;
29
  }
30

31
  let newNode = new ListNode(val);
32
  newNode.next = this.head;
33
  this.head.prev = newNode;
34
  this.head = newNode; // the new node becomes the new head
35
  this.len += 1;
36
};
37

38
/**
39
 * @param {number} val
40
 * @return {void}
41
 */
42
FrontMiddleBackQueue.prototype.pushMiddle = function (val) {
43
  if (this.len <= 1) {
44
    this.pushFront(val);
45
    return;
46
  }
47
  let cur = this.head;
48
  for (let i = 1; i < Math.floor(this.len / 2); i++) {
49
    // we go to previous node of median
50
    cur = cur.next;
51
  }
52
  let newNode = new ListNode(val);
53
  let next = cur.next;
54
  cur.next = newNode;
55
  newNode.prev = cur;
56
  newNode.next = next;
57
  if (next) next.prev = newNode;
58
  this.len += 1;
59
};
60

61
/**
62
 * @param {number} val
63
 * @return {void}
64
 */
65
FrontMiddleBackQueue.prototype.pushBack = function (val) {
66
  if (this.len === 0) {
67
    this.pushFront(val);
68
    return;
69
  }
70

71
  let newNode = new ListNode(val);
72
  this.tail.next = newNode;
73
  newNode.prev = this.tail;
74
  this.tail = newNode; // end node becomes the new tail
75
  this.len += 1;
76
};
77

78
/**
79
 * @return {number}
80
 */
81
FrontMiddleBackQueue.prototype.popFront = function () {
82
  if (this.len === 0) {
83
    return -1;
84
  }
85
  let front = this.head;
86
  let next = front.next;
87
  if (next) next.prev = null;
88
  this.head = next;
89
  this.len -= 1;
90
  return front.val;
91
};
92

93
/**
94
 * @return {number}
95
 */
96
FrontMiddleBackQueue.prototype.popMiddle = function () {
97
  if (this.len <= 2) {
98
    return this.popFront();
99
  }
100
  let cur = this.head;
101
  for (let i = 1; i < Math.ceil(this.len / 2); i++) {
102
    // we go to median node
103
    cur = cur.next;
104
  }
105

106
  let prev = cur.prev;
107
  let next = cur.next;
108
  cur.prev = null;
109
  cur.next = null;
110
  if (prev) prev.next = next;
111
  if (next) next.prev = prev;
112
  this.len -= 1;
113
  return cur.val;
114
};
115

116
/**
117
 * @return {number}
118
 */
119
FrontMiddleBackQueue.prototype.popBack = function () {
120
  if (this.len <= 1) {
121
    return this.popFront();
122
  }
123
  let end = this.tail;
124
  let prev = end.prev;
125
  end.prev = null;
126
  prev.next = null;
127
  this.tail = prev;
128
  this.len -= 1;
129
  return end.val;
130
};
131

132
/**
133
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
134
 * var obj = new FrontMiddleBackQueue()
135
 * obj.pushFront(val)
136
 * obj.pushMiddle(val)
137
 * obj.pushBack(val)
138
 * var param_4 = obj.popFront()
139
 * var param_5 = obj.popMiddle()
140
 * var param_6 = obj.popBack()
141
 */