Linked Lists

Linked Lists

Linked Lists

• A sequence of Nodes that are connected/linked to each other
  • The most defining feature of a Linked List is that each Node references the next Node in the link
• Two types of Linked List - Singly and Doubly
  • Singly refers to the number of references the node has. A Singly linked list means that there is only one reference, and the reference points to the Next node in a linked list
  • Doubly refers to there being two (double) references within the node. A Doubly linked list means that there is a reference to both the Next and Previous node
• You are not able to use a foreach or for loop
• 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
  • If we accidentally end up trying to traverse on a node that is null, a NullReferenceException gets thrown and our program will crash/end

Big O

• The Big O of time for Includes would be O(n)
  • This is because, at its worse case, the node we are looking for will be the very last node in the linked list
  • n represents the number of nodes in the linked list
• The Big O of space for Includes would be O(1)
  • This is because there is no additional space being used than what is already given to us with the linked list input

What’s a Linked List, Anyway pt1

• Data structures, which are the different ways that we can organize our data
  • Ex. Variables, arrays, hashes, and objects
• 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
• Linked lists don’t need to take up a single block of memory; instead, the memory that they use can be scattered throughout
• Linked lists are dynamic data structures
  • A dynamic data structure can shrink and grow in memory
• The starting point of the list is a reference to the first node, which is referred to as the head
• The end of the list isn’t a node, but rather a node that points to null, or an empty value
• A single node has two parts:

  • Data, or the information that the node contains

  • A reference to the next node

     `A node only knows about what data it contains, and who its neighbor is`
    

What’s a Linked List, Anyway pt2

• An O(1) function takes constant time, which is to say that it doesn’t matter how many elements we have, or how huge our input is: it’ll always take the same amount of time and memory to run our algorithm
• An O(n) function is linear, which means that as our input grows (from ten numbers, to ten thousand, to ten million), the space and time that we need to run that algorithm grows linearly
• An O(n²) function, which clearly takes exponentially more time and memory the more elements that you have
• A linked list is usually efficient when it comes to adding and removing most elements, but can be very slow to search and find a single element