Intro DS: Linked Lists
Introduction to Linked Lists in JavaThis first video shows the basics of a linked list.
This next video shows you how to implement a linked list in java.
The following articles also give an excellent overview of Linked List data structures. Please read them carefully.
Run Times of Linked Lists vs. Arrays
|Retrieve kth element in a list of n elements.||O(n)||O(1)||The array permits random access whereas the LL requires sequential processing.|
|Insert at front of list||O(1)||O(n)||For the array case, all the subsequent members need to be shifted down one position.|
|Insert at end of list||O(n)||O(1)||While the actual insertion into the LL takes O(1) time only, getting to the last node consumes O(n) time.|
|Search for an element.||O(n)||O(n)/O(log(n))||A linear search requires O(n) time. However, if the array is sorted, a binary search can be used requiring O(log(n)) time.|
|Delete all instances of an element.||O(n)||O(n)||A linear search requires O(n) time for both implementations.|