The book continues to the # linked list algorithm analysis – JS chapter, the last chapter is the definition of linked list, and some simple linked list algorithm questions.
Because helplessly painful JS has no built-in LinkList… So in this chapter we will design a linked list ourselves, which is also LeetCode problem 707, and need to implement the following methods:
- Get (index) : Gets the value of the index node in the list. If the index is invalid, -1 is returned.
- AddAtHead (val) : Adds a node with the value val before the first element of the list. After insertion, the new node becomes the first node in the linked list.
- AddAtTail (val) : Appends a node with the value val to the last element of the list.
- AddAtIndex (index,val) : Adds a node with the value val before the index node in the linked list. If index is equal to the length of the list, the node is appended to the end of the list. If index is greater than the list length, no node will be inserted. If index is less than 0, insert the node in the header.
- DeleteAtIndex (index) : Deletes the index of the list if the index index is valid.
Example:
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1.2); // The list changes to 1-> 2-> 3
linkedList.get(1); / / return 2
linkedList.deleteAtIndex(1); // Now the list is 1-> 3
linkedList.get(1); / / return 3
Copy the codethinking
What needs to be provided in the instance function to satisfy these methods?
Because the get, addAtIndex, and deleteAtIndex functions need to determine whether the index is valid or not, if we don’t have the length of the list, we have to loop through the length every time, which is very time-consuming, so we define the length of the list this.size.
Since we are implementing addAtHead to add nodes to the header, we define a header pointer this.head.
Since we’re implementing addAtTail, adding nodes to the end of the list would be a waste of time if we were to iterate over the end of the list with a pointer to this.tail.
Code implementation
var MyLinkedList = function () {
this.size = 0;
this.head = null;
this.tail = null;
};
/ * * *@param {number} index
* @return {number}* /
MyLinkedList.prototype.get = function (index) {
if (index >= this.size) return -1;
let ans = this.head;
while (index) {
ans = ans.next;
index--;
}
return ans.val;
};
/ * * *@param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtHead = function (val) {
const node = new ListNode(val, this.head);
if (!this.size) {
this.tail = node;
}
this.head = node;
this.size += 1;
};
/ * * *@param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtTail = function (val) {
const node = new ListNode(val, null);
if (!this.size) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = this.tail.next;
}
this.size += 1;
};
/ * * *@param {number} index
* @param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtIndex = function (index, val) {
if (index > this.size) {
return
} else if (index === this.size) {
this.addAtTail(val)
} else if (index <= 0) {
this.addAtHead(val)
} else {
index -= 1;
let current = this.head;
let idx = 0;
while (idx < index) {
current = current.next;
idx++;
}
const next = current.next;
current.next = new ListNode(val, next);
this.size += 1; }};/ * * *@param {number} index
* @return {void}* /
MyLinkedList.prototype.deleteAtIndex = function (index) {
if (index >= this.size) return;
if (index === 0) {
this.head = this.head.next;
this.size -= 1;
return;
}
let current = this.head;
while (index > 1) {
current = current.next;
index--;
}
if (current.next === this.tail) {
this.tail = current;
}
current.next = current.next.next;
this.size -= 1;
};
function ListNode(val, next) {
this.val = val;
this.next = next || null;
}
/** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */
Copy the codeSentinel nodes and double-linked lists
What are some error-prone or optimized points in the above code?
- AddAtHead and addAtTail determine whether the length is empty and initialize the head and tail nodes
- In the deleteAtIndex
if (current.next === this.tail) { this.tail = current; }This code needs to move the tail node - When querying nodes, if the node we need to operate on is at the end, we also need to traverse the linked list from the beginning
So how to solve it?
- Sentinel node, simulate a virtual pseudo head and pseudo tail node, such that the operation time of both the head and tail is O(1)
- O(min(index, size-index))
var MyLinkedList = function () {
this.size = 0;
const dump_head = new ListNode(-1);
const dump_tail = new ListNode(-1);
dump_head.next = dump_tail;
dump_tail.prev = dump_head;
this.head = dump_head
this.tail = dump_tail;
};
/ * * *@param {number} index
* @return {number}* /
MyLinkedList.prototype.get = function (index) {
if (index >= this.size) {
return -1;
}
if ((index + 1) * 2 > this.size) {
// Close to the tail
let idx = this.size - index;
let current = this.tail;
while (idx) {
current = current.prev;
idx--;
}
return current.val;
} else {
let idx = index + 1;
let current = this.head;
while (idx) {
current = current.next;
idx--;
}
returncurrent.val; }};/ * * *@param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtHead = function (val) {
const next = this.head.next;
const node = new ListNode(val, next, this.head);
next.prev = node;
this.head.next = node;
this.size++;
};
/ * * *@param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtTail = function (val) {
const prev = this.tail.prev;
const node = new ListNode(val, this.tail, prev);
this.tail.prev = node;
prev.next = node;
this.size++;
};
/ * * *@param {number} index
* @param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtIndex = function (index, val) {
if (index > this.size) {
return
} else if (index === this.size) {
this.addAtTail(val)
} else if (index <= 0) {
this.addAtHead(val)
} else {
let idx = 0, current = null;
if ((index + 1) * 2 > this.size) {
idx = this.size - index;
current = this.tail;
while(idx) { current = current.prev; idx--; }}else {
idx = index + 1;
current = this.head;
while(idx) { current = current.next; idx--; }}const prev = current.prev;
const node = new ListNode(val, current, prev);
prev.next = node;
current.prev = node;
this.size++; }};/ * * *@param {number} index
* @return {void}* /
MyLinkedList.prototype.deleteAtIndex = function (index) {
if (index >= 0 && index < this.size) {
let idx = 0, current = null;
if ((index + 1) * 2 > this.size) {
idx = this.size - index;
current = this.tail;
while(idx) { current = current.prev; idx--; }}else {
idx = index + 1;
current = this.head;
while(idx) { current = current.next; idx--; }}const prev = current.prev;
const next = current.next;
prev.next = next;
next.prev = prev;
this.size--; }};function ListNode(val, next, prev) {
this.val = val || 0;
this.next = next || null;
this.prev = prev || null;
}
/** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */
Copy the codeThe code of this article has been included in Github, the warehouse includes the previous article links and code included, the subsequent code will be updated, welcome your comments.