Singly Linked List

Objectives

1. Define what a Singly Linked List is.
2. Compare and contrast Linked Lists with Arrays
3. Implement Insertion, removal and traversal methods on Singly Linked Lists

What is a linked list?

it's a data structure that stores whatever data you want, strings, numbers, ... and it's ordered, it's a list of data just like an array. But there's a really big distinction. in an array each item is mapped it's indexed with a number. So I can get the 5th item 6th item and anytime we add something in, it gets an index that map to its position, a linked list on the other hand just consists of a bunch of elements with no indicies who are just pointing to the next element. sort of like a bunch of train cars connected where one car connects to the next one and that one connects to the next one and so on... But, there is no index that we use to access things. we say that each element is a node, so a linked list consists of a bunch of nodes. a node stores a piece of data like string, number, but it also references the next node and at the end it references to null

. A data structure that contains a head, tail and length property.

head => is the beginning of the linked list tail => is the end

so we don't keep track of every single item in the middle, we just keep track of the head and from the head we can figure out the next one. And also we keep track the length to make things easier.

singly linked list comes from the fact that each node is only connected one directionally to the next node.

Doubly Linked List Also has a connection pointing back to the previous node and we'll talk about the pros and cons to that.

Comparisons with Arrays

Lists

. Do not have indexes! . Connected via nodes with a next pointer . Random access is not allowed!

Arrays

. indexed in order! . Insertion and deletion can be expensive . Can quickly be accessed at a specific index

One of the things which Linked List are good at, is insertion and deletion

because arrays are indexed, if we insert something at the beginning or in the middle we've already talked about this. everything has to be re-indexed. in a linked list that's not the case

So main reason you wanna use linked list, if you really care about the insertion and deletion, specially if you work with really really long pieces of data set and you don't need random access you just need to store it in a list.

Started Code and push Intro

Remember that a linked list is just a collection of nodes. so let's defining a class for each node.

// piece of data - val
// reference to next node - next

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val) {
    
  }
}

const list = new SinglyLinkedList();
list.push("Hello");
list.push("GoodBye");

Pushing

Adding a new node to the end of the Linked List!

Pushing pseudocode

. This function should accept a value . Create a new node using the value passed to the function . If there is no head property on the list, set the head and tail to be the newly created node . Otherwise set the next property on the list to be the newly created node . Increment the length by one . Return the linked list

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val) {
    var newNode = new Node(val);
    if(!this.head) {
       this.head = newNode;
       this.tail = this.head;
    } else {
       this.tail.next = newNode;
       this.tail = newNode;
    }
    this.length++;
    return this;
  }
}

var list = new SinglyLinkedList();