Intro DS: Linked Lists

Introduction to Linked Lists in Java

This 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.


http://computationaltales.blogspot.com/2011/04/linked-lists-kindergarten-and-ocean.html


http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html


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(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.