Arrays and Linked Lists

Algorithms and Data Structures From Zero to Hero

  • You may not need extra slots that you asked for, and then that memory will be wasted.
  • You may add more than 10 items to your expense list and have to move anyway.

Linked lists

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

Sequential vs Random Access

Sequential access means the cost of accessing the 5th element is 5 times the cost of accessing the first element, or at least that there is an increasing cost associated with an elements position in the set. This is because to access the 5th element of the set, you must first perform an operation to find the 1st, 2nd, 3rd, and 4th elements, so accessing the 5th element requires 5 operations.

Array vs LinkedList

Array vs Linkedlist

Arrays

Arrays are better than linked list when we try to access to our items in the list.

Inserting into the middle of a list

Suppose you want your expense list to work more like a calendar. Earlier, you were adding things to the end of the list.

Deletions

What if you want to delete an element? Again, linked lists are better, because you just need to change what previous element points to. With arrays everything needs to be moved up when you delete an element.

Run times for common operations on arrays and list:

Run times for common operations

EXERCISES

Suppose your’e building an app for super market to take customer orders. Your app needs to store a list of orders. customers keep adding orders to this list, and the employees take orders off the list and make them. It’s an order queue: customers add orders to the back of the queue, and the employe takes the first order off the queue and prepare it.

Next

Arrays and linked list are used to implement other data structures, too.

--

--

Sometimes I write about technical topics and sometimes about what I feel like.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kemil Beltre

Sometimes I write about technical topics and sometimes about what I feel like.