Non-Primitive Data Structures

Data Structures can be broadly classified into primitive and non-privative types.

Primitive data structures are the basic data structures that typically hold singular points of data. They can be defined as data that is not an object and has no methods. In Javascript there are 7 primitive data types: string, number, bigint, boolean, undefined, symbol, and null.

Non-Primitive data structures are more complicated, usually comprised of primitive data types grouped in ways to enable efficient management of larger sets of data based on the relationship between them.

Arrays

An Array is a linear collection of data elements having the same data type.

• Accessing an element: O(1) This is the primary advantage of an array because it stores elements at known location
• Search an element: O(n)
• Insertion of an Element: O(n)
• Deletion of an Element: O(n)

Advantages and Disadvantages of an Array:

1. Accessing a known element is fast because the location is already known. You would not need to traverse an array like with a linked list.
2. Insertion and deletion can be expensive because an entire array may need to be modified when only one element needs to be changed.
3. In most languages arrays need to be contiguous. This often means that an array size will need to be predetermined when it is created. Modifying an array above its size means that a new array will need to be created of the new size.

Linked Lists

A Linked list is a collection of nodes, where each node has a data element and a reference to the next and/or previous node in the sequence.

Singly linked list

Singly linked list stores data and the reference to the next node or a null value.

Doubly linked list

It has two references, one for the last node and one for the previous node. This helps us traverse in both the directions.

• Accessing an element: O(n)
• Search an element: O(n)
• Insertion of an Element: O(1)
• Deletion of an Element: O(1)

Advantages and disadvantages of Linked Lists:

1. Linked Lists allow for faster insertion and deletion and modification of the list as reference pointers can easily be modified to snip or redirect the linked list
2. Random known elements cannot be as easily accessed as it requires the traversal of possibly the entire array to access the data at the needed location.
3. Extra memory is required to store not only the data, but the reference pointers as well, doubly so for double linked lists

Stack

• A Stack is a FILO (First In Last Out) data structure where the element that is added first will be deleted last.

It allows two operations — Push and Pop. Push allows us to add elements to the top while Pop allows removing the last element (removing the element at the top). Both operations can take place at the same end.

• Accessing an element: O(n)
• Search an element: O(n)
• Insertion of an Element: O(1)
• Deletion of an Element: O(1)

Example:- As we navigate from one web page to another, those pages are placed on a stack. The current page is on the top and the first page we looked at is at the bottom of the stack. If we click on the back button, we begin to move in reverse order through the pages.(Popping each page).

Queues

• A Queue is a FIFO (First in First Out) data structure where the element that is added first will be deleted first.

It is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer.

• Accessing time of an element: O(n)
• Search time of an element: O(n)
• Insertion of an Element: O(1)
• Deletion of an Element: O(1)

Examples of a queue might be a ticketing system, a input stream or something like a printer queue.

Trees

A tree is a non-linear data structure that can be defined as a collection of nodes where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”). It is similar to a linked list, but instead of referencing just one next object it can reference multiple child objects.

• Search an element: O(n)
• Insertion of an Element: O(n)
• Deletion of an Element: O(n)

Graphs

A graph is a common data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them.

Types of graphs:

Undirected Graph:

In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.

Directed Graph

In a directed graph, nodes are connected by directed edges — they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 — not in the opposite direction.