Formal Definition

• When you search on google "What is a linked list ?" You will get answer
  • A linked list is a linear data structure consisting of nodes, where each node contains data and a reference (link) to the next node in the sequence

Before Understanding A definition Lets Find Out Why Even Learn Linked List in a first place ?

• Why would someone invent a linked list when array already solves the problem of storing data ?

• To understand why learn linked list. We must understand what are some of the limitations of array.

  1. Problem #1 - Array is stored in contiguous memory location
  Array value

  Other data

  Free

  Just added

  0x0010

  0x0120

  0x0230

  0x03—

  0x04busy

  0x05busy

  0x06—

  0x07—

  0x08busy

  0x09busy

  0x0Abusy

  0x0B—

  Array [10, 20, 30] stored in 3 consecutive slots starting at 0x00.

  Add element →Reset

  I hav given a detailed animated, description on what happens if the data are stored in contiguous memory location. There is an array of size 3, if you add 40 then 40 gets added because free space is available. but you can see that memory location 0x04 is busy, which means value can't be stored over there.

  ---

  2. Problem #2 - Insertion is expensive

  Original array

  [0]10

  [1]20

  [2]30

  [3]40

  [4]50

  Unchanged

  Shifting

  Inserted

  Empty slot

  We want to insert 25 at index 2 into [10, 20, 30, 40, 50].

  Next step →Reset
  • generate a jsx code that shows insertion is expensive in array because you have to shift the entire array
  • Lets take example as arr = [10,20,30,40,50] . If you want to insert 25 at index 2. then you have to shift the entire array from that index.

Advantage Of Linked List

• Advantage of linked list is that it solves the problem faced by array. But just to make things clear. I will list out few importances
  1. Insertion and deletion is fast.
     • insertion and deletion is fast because you don't have to shift the entire list. You just insert wherever you want and link to it.
     • // Show the diagram for linked insertion and deletion is fast
  2. It is not stored in contiguous memory location
  Linked list node

  Other data

  Free

  row 1

  0x0010→0x07

  0x01busy

  0x02busy

  0x03busy

  0x04—

  0x05busy

  0x06busy

  row 2

  0x0720→0x0B

  0x08busy

  0x09—

  0x0Abusy

  0x0B30→null

  0x0Cbusy

  0x0D—

  Node 1 lives at 0x00 and points to 0x07

  Node 2 lives at 0x07 and points to 0x0B

  Node 3 lives at 0x0B — no next node, next = null

  No consecutive slots needed. Each node just remembers where the next one lives.

  • Advantage of not storign data in contiguous memory location is that, suppose your data is of 10 byte and only 5 byte is left then they can be store where the memory is free and they can be linked like a chain // generate a diagram representing this.

Designing A Linked List

• We now have basic idea that array has few limitations, main limitations was
  1. contiguous memory location
  2. Insertion is expensive because you have to shift the entire array
• Now we will be learning how to design a linked list and how it solves the problem faced by array.
• Before directly jumping into writing code. Lets first understand What are the things that are required to create a linked list or terminologies used in linked list.

Terminologies Used in Linked list

1. Node
2. Head
3. Tail
4. Data
5. Next

1. Node

• We know that array stores only value.Fore eg: array stores values / data like [1,2,3] or ["abc", "xyz"] , etc
• But linked list has Node.Node = Data + Address of next

  one node

  42data

  actual value stored

  0x07next

  address of next node

  → points to next node

  ?next node at 0x07

  Key idea: Every node carries two things — the value you care about, and a breadcrumb to the next node. When next is null, you've reached the end.
  • Data is the actual data, like numbers 1 , 2 ,3 that you have already seen while creating an array. And address is the memory location where next data / value is stored.
  • For eg: You have 4 friends. You know the address of friend-1 and friend-1 knows the address of friend-2 and friend-2 knows the address of friend-3 and friend-3 knows the address of friend-4. How can you go to friend-4 ? One idea that may strike you is that you will go to friend-1 and ask the location of next friend. your next friend or you will go to friend-2 and ask the location of friend-3 and you repeat the process, until you find the location of friend-4. This is what you are exactly doing in linked list.
  • Node has data and address of next Node. You can access the first data, you will be given address of next Node, with the help of that address you can find where another data is.

2. Head

• We already discussed about Node, Its [Data + Address] right ? So the first node is called as head.

3. Tail

• Last node is called as tail

4. Data

• data is the actual value that is being stored

5. Next

• Remember your friends address. It is similar to that. It is the address in memory location.

How can we create a Node

• I won't be diving deep into Object Oriented Programming here. But just a small hint is that whenever you have to create your own custom data type. You use class
• Node is our custom data type, which consists of Data and Addres (Next). So, we will be using class to create a node

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

• We are pointing this.next = null because it doesn't have any connection. Its a stand alone data.