switch(position)
case 0:
head = head.next
case list.length - 1:
current = tail.prev
current.next = none
tail = current
default:
current = head
index = 0
if(list.length / position >= 2)
while(index + 1 != position)
current =
current.
next
index += 1
nextNext = current.next.next
current.
next = nextNext
else
current = tail
index = list.length
- 1
while(index - 1 != position)
current =
current.
prev
index -= 1
prevPrev = current.prev.prev
current.
prev = prevPrev
---------------------
| SHORT EXPLANATION |
---------------------
1. Determine which node will be removed
- if it's the head, just update the head pointer
- if it's the tail, update the tail pointer
2. If it gets removed from index N, determine if it's
faster to get to the node from the tail or the head
3. Traverse the list up to the node before or after the one
which will be removed (depends on the direction)
4. Remove the node which was supposed to be removed
5. Update the 'next' and 'prev' pointers of the nodes
coming before and after the one which was just removed
respectively
---------------------------
| Time
complexity: |
| Remove head:
O(1) |
| Remove tail:
O(1) |
| Remove from index: O(n) |
---------------------------
switch(position)
case 0:
node.next =
head
head.prev =
node
head = node
case list.length:
tail.next =
node
node.prev =
tail
tail = node
default:
current = head
index = 0
if(list.length / position >= 2)
while(index != position - 1)
current =
current.
next
index += 1
else
current = tail
index = list.length
- 1
while(index != position)
current =
current.
prev
index -= 1
node.next =
current.next
node.
prev = current
current.
next = node
---------------------
| SHORT EXPLANATION |
---------------------
1. Determine where the new node will be inserted
- if it becomes the new head, overwrite the current head
after saving it as the node's successor
- if it's the new tail, set it as the successor of the
current tail
2. If it gets inserted at index N, determine if it's faster
to get to that position from the tail or the head
3. Traverse the list up to one node before or after the
position where the new node will be inserted (depends on the
direction)
4. Add the new node
5. Update the 'next' and 'prev' pointers of the nodes
coming before and after the one which was just added
respectively
-------------------------
| Time
complexity: |
| Insert as head: O(1) |
| Insert as tail: O(1) |
| Insert at index: O(n) |
-------------------------
current = head
index = 0
while(current.data != data)
if(current.
next == none)
return -1
current = current.next
index += 1
return index
SHORT EXPLANATION
-----------------
1. Traverse the list until element is found or the whole
list has been traversed
- if element was found, return index
- else return not_found
Time complexity
Find element: O(n)