Array vs Linked List
- Access an item: In an array, you can access an element with the index. If you want to access the third element you have to write the variable number with its index in the square bracket. Lists, on the other hand, do not support random access. To access the third item you have to start from the head and walk your way through until you reach the third element.
- Insertion: Inserting an element into the array is slow. If you want to insert an item in the fourth position, you have to move all items after the third position to the right by one position to leave space for the new inserted item. This takes linear time. Whereas, in a linked list, you could insert an item in constant time if you are given a pointer that points to the previous value before the position you want to insert the element. You just change its next pointer to point to the new element and set the new item's next pointer to point to the rest of the list.
- Deletion: similar to insertion, the linked list deletes an item much faster than the array. You just set the next pointer of the previous node to point to the rest of list after the deleted node.
Toolkit
The following is some useful member functions of linked lists that you could implement when you build your own linked list class.
- Length
- Find an element at a particular position
- Insert a value at the beginning or end
- Insert somewhere other than the beginnig or end
- Remove head or tail
- Remove other than head or tail
- Remove the first element in the list that has a paticular value
- Remove all elements with a particular value
- Remove all elements from a list
- Create a copy of list
- Append one list onto another(non-destructive)
