View reading-notes on GitHub

Linked Lists && Big O

Big O: Analysis of Algorithm Efficiency

  • Big O(oh) notation is used to describe the efficiency of an algorithm or function. This efficiency is evaluated based on 2 factors

  • Big O: The worst case analysis of algorithm efficiency.
  • Running Time: The amount of time required for an algorithm to complete.
  • Memory Space: The amount of memory resources required for an algorithm to complete.
  • Input Size: Represented by the variable n, the total size of values used as parameters in an algorithm.
  • Big Omega: The best case analysis of algorithm efficiency.
  • Big Theta: The typical or random case used for analysis of algorithm efficiency.

Linked Lists

What does it look like?

linkedlist

  • A Linked List is 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.

  • There are two types of Linked List - Singly and Doubly. We will be implementing a Singly Linked List in this implementation.

data structures

  • In computer science, 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. It is a data structure consisting of a collection of nodes which together represent a sequence.

Types of linked lists

  • Singly linked list
  • Doubly linked lists
  • Circularly linked lists

Memory management

  • The biggest differentiator between arrays and linked lists is the way that they use memory in our machines. Those of us who work with dynamically typed languages like Ruby, JavaScript, or Python don’t have to think about how much memory an array uses when we write our code on a day to day basis because there are several layers of abstraction that end up with us not having to worry about memory allocation at all. Memory management

Linked List?

  • O(1) : means i need a constant time & and same space, and doesn’t matter how much the elements we have or how huge our input is.
  • O(n) : means that as our input grows, the space and time that we need to run that algorithm grows linearly.
  • 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. data structures : ways of organizing our data.
  • linked lists are a linear data structure, that means we traversed over the data sequentially.
  • arrays and linked lists are linear data structure.

How structure is used in linked list?

  • Insert node at the beginning.
  • Insert node in the middle
  • Insert node at the end

Example of Linked List !!

To list or not to list?

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