reading-notes

Linked Lists

A Linked List is a sequence of Nodes that are connected/linked to each other.

each Node references the next Node in the link.

Singly - Singly refers to the number of references the node has.

What does it look like

Traversal

The Next property is exceptionally important because it will lead us where the next node is and allow us to extract the data appropriately.

The best way to approach a traversal is through the use of a while() loop. This allows us to continually check that the Next node in the list is not null

When traversing through a linked list, the Current variable will tell us where exactly in the linked list we are and will allow us to move/traverse forward until we hit the end.

Traversal Big O

The Big O of time for Includes would be O(n).

The Big O of space for Includes would be O(1).

Adding O(1)

Here are the required steps to add a new node with an O(1) efficiency.

1- We can then instantiate the new node that we are adding.

2- newNode.Next by default is set to null.

3 - we want to re-assign Head to point at newNode

What’s a Linked List, Anyway? [Part 1]

Linear data structures

One characteristic of linked lists is that they are linear data structures, which means that there is a sequence and an order to how they are constructed and traversed

Memory management

Linked lists don’t need to take up a single block of memory; instead, the memory that they use can be scattered throughout.

Parts of a linked list

A linked list is made up of a series of nodes

What’s a Linked List, Anyway? [Part 2]

Hey, so, what even is Big O?

There are two major points to consider when thinking about how an algorithm performs: how much time it requires at runtime given how much time and memory it needs.

One way to think about Big O notation is a way to express the amount of time that a function, action, or algorithm takes to run based on how many elements we pass to that function.

Growing a linked list

Inserting an element at the beginning of a linked list is particularly nice and efficient because it takes the same amount of time, no matter how long our list is, which is to say it has a space time complexity that is constant, or O(1).