Intro DS: Linked Lists

Introduction to Linked Lists 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

Algorithm Linked List Array Description
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(n*log(n)) A linear search requires O(n) time. However, if the array is sorted, a binary search can be used requiring O(n*log(n)) time.
Delete all instances of an element. O(n) O(n) A linear search requires O(n) time for both implementations.