switch(position)
case 0:
head = head.next
case list.length - 1:
current = head
index = 0
while(current.
next
!= tail)
current = current.
next
index += 1
current.next
= none
tail = current
default:
current = head
index = 0
while(index + 1 != position)
current = current.
next
index += 1
nextNext = current.next.next
current.
next = nextNext
---------------------
| SHORT EXPLANATION |
---------------------
1. Determine which node will be removed
- if it's the head, just update the head pointer
- if it's the tail, traverse the list and set the sucessor
of the node before the tail to none
2. If it gets removed from index N, traverse the list up to
node N-1 and get the node after the node it points to
3. Point the 'next' pointer of the node at N-1 to the node
obtained in step 2
Time complexity:
Remove head: O(1)
Remove tail: O(n)
Remove from index: O(n)
switch(position)
case 0:
node.next =
head
head = node
case list.length:
tail.next =
node
tail = node
default:
current = head
for(i = 0 to
position - 1)
current = current.
next
node.next =
current.next
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, traverse the list up to
node N-1 and get the node it points to
3. Point the 'next' pointer of the new node to the node
obtained in step 2
4. Point the 'next' pointer of the node at index N-1 to the
new node
Time complexity:
Insert as head: O(1)
Insert as tail: O(1) if you keep pointer to the tail, O(n)
else
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)