Data Structures: Linked lists

Question 1

What are nodes?

Answer 1

Nodes are the most foundational elements of data structures.

Nodes are self-referential as they include a reference to objects of the same type

Question 2

What do nodes contain?

Answer 2

data and a link (pointer to another node)

Nodes can contain a lot of elements, but only one link.

Question 3

What does it mean if a link or pointer’s value is null

Answer 3

If these links are null, it denotes that you have reached the end of the particular node or link path

Question 4

What is an orphaned node?

Answer 4

A node whose links have been severed which results in it’s data being lost to the application

Question 5

6 primitive data types

Answer 5

Boolean
Number
String
BigInt
Symbol
undefined

Question 6

3 Special data types

Answer 6

null
Object
Function

Question 7

What is a linked list?

Answer 7

Is a list of nodes connected in series. The first node is called the head and the last node is called the tail. LInked lists typically contain unidirctional links (next node), but some implementations make use of biderectional links

common opperations inlcude:

• adding a node
• removing a node
• finding a node
• traversing the list

Question 8

Why we need pointers in Linked List, but not for arrays?

Answer 8

In case of array, memory is allocated in contiguous manner, hence array elements get stored in consecutive memory locations. So when you have to access any array element, all we have to do is use the array index, for example arr[4] will directly access the 5th memory location, returning the data stored there.

But in case of linked list, data elements are allocated memory at runtime, hence the memory location can be anywhere. Therefore to be able to access every node of the linked list, address of every node is stored in the previous node, hence forming a link between every node.

We need this additional pointer because without it, the data stored at random memory locations will be lost. We need to store somewhere all the memory locations where elements are getting stored.

Yes, this requires an additional memory space with each node, which means an additional space of O(n) for every n node linked list.

Question 9

Different kinds of linked lists

Answer 9

Single linked lists: Navigation is forward only

Doubly linked lists: Navigation is forward and backward

Circular linked lists: The last element is linked to the first element