Skip to content

Latest commit

 

History

History
87 lines (49 loc) · 4.38 KB

1.INTRO_LINKED_LISTS.md

File metadata and controls

87 lines (49 loc) · 4.38 KB
Raw

LINKED LISTS

link trains

Puff a Train | Nursery Rhyme GIF

What are Linked Lists?

Let us begin with the Oxford Language Dictionary defintion for Link:

"[transitive] to make a physical or electronic connection between one object, machine, place, etc. and another synonym connect."

  • Example 1: "Linked Toy Train Carts".

  • Example 2: "A link of people holding hands".

  • Example 3: A Music Player that cycles through a playlist.

    • Keep these examples in mind as you read through and try and make connections between them. Especially a music player.

Linked Lists for Software are no different from the day-to-day verb we use for link. The unique difference is the usage it has in the aspect of Software creation:

Linked Lists in Software Programming are a method of storing data and have different parts that can glue data together.

There are different types of linked lists: Singly Linked, Doubly Linked Lists, & Circular linked lists. I will only focus on Doubly Linked Lists:

A. Doubly Linked List:

    - Node: an element that contains information. A Node has a Value and Pointers.
    - Head/Tail: Head or Tail can be asigned to the First/Last Node you want to refer to on your Linked List. 
    - Value: the specific information inside the Node.
    - Pointer: what links nodes together. Or the glue. You can have a NEXT (pointing to the next Node) or a PREVIOUS (pointing to the previous NODE).

Here is a visual for you:

Linked List Graphics by @thunderbionk

Why are they important?

Many programs we use today require the usage of Linked Lists so we can keep track of data locations in memory efficiently. Different from Stacks, Linked Lists are dynamic, which makes them the best choice when it comes to keeping track, adding, or removing data while running a program.

When do we use them?

Pause for a moment and think of Software that allows you use Linked Lists. Here is a common situation:

SITUATION A: Keeping track of a song that is currently playing (Active Node), the previous song(History), and the next song(Queue). Observe that you can define the order in which you play music from A-Z, date added (if available), by Artist, by Genre, etc. This implies that each time you reorganize the way you play music, the Songs(Nodes or Data) remain, it's just the pointers that change spots to change according to the order in which you will listen to music.

  1. Music Apps: Music Apps like Soundcloud, Spotify, iTunes, Amazon Music, etc., all use this data structure when it comes to shuffling your music and reorganizing the order in which you listen to it. Same with being able to keep track of the Music History, or your Queue. Notice that adding a song to the queue and changing it's spot to be the Last played song on the queue to be the Next song on the queue is a great example of Pointers being changed in the Linked List.

    Watch this video on Linked Lists in Music PLayers to see how this looks like in the User Interface for Apple Music

    Linked Lists in Music Player

O - Notation for Linked Lists Operations

It is good for you to be able to identify Linked List Operations in order to determine their Algorithmic Efficiency when debugging or building different types of Software:

The common O - Notation Linked Lists Operations are the following:

DYNAMIC ARRAYS:

  • O(n) operators: Insert Front/Middle, Remove Front/Middle.
  • O(1) operators: Insert End/Remove End.

Linked List:

  • O(n) operators: Insert Middle, Remove Middle.

  • O(1) operators: Insert Front/End, Remove Front/Remove End.

    O_notation Linked Lists Graphics by @thunderbionk

Examples:

Back to main README