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

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