LINEAR DATA STRUCTURES

linear data structure

a data structure where elements are organized sequentially, wherein each element is positioned in a linear order, and traversal typically follows one direction (from start to end).

array

a fixed-length, ordered collection of values of the same type stored in contiguous memory locations. The collection may be ordered in several dimensions.

Static arrays

data structures with a fixed size. Once an array is created, its size cannot be changed or altered.

Fixed Size

The size of the array is set during the declaration and cannot be modified.

Memory Allocation

The memory is located on the stack, which is faster but has a limited size.

Access Time

The elements can be accessed in constant time since the address of the elements can be calculated using the base address and the index.

Usage

It is ideal for scenarios where the number of elements is known beforehand, such as storing fixed-sized data like days of the week and months of the year.

Dynamic Array

resizable arrays, can change size during runtime.

Resizable

The array can be resized, allowing it to grow or shrink based on the requirements

Memory Allocation

The memory is allocated on the heap, which is more flexible but can be slower due to the overhead of dynamic memory management.

Access Time

Similar to static arrays, elements can be accessed in constant time after they are created.

Usage

It is useful when the number of elements is not known in advance or when the array needs to expand during program execution.

linked list

consists of chains of nodes, where each node contains information, such as data, and a pointer to the next node. Each node is composed of data and a reference (a link) to the next node in the sequence; more complex variants add additional links.

Singly Linked List

consists of nodes where each node contains a data field and a reference to the next node in the linked list. The next of the last node is null, indicating the end of the list.

Doubly Linked List

a more complex data structure than a singly linked list. It allows for efficient traversal of the list in both directions, as each node in the list contains a pointer to the previous node and a pointer to the next node.

Traversal

It means visiting each node in the linked list one by one to read, display, or process its data.

Insertion

It means adding a new node to a linked list. It’s one of the core operations supported by all types of linked lists.

Deletion

It is the operation of removing a node from a linked list.

Search

It means finding a node that contains a specific value by traversing each node one-by-one starting from the head.

Sort

It means arranging its nodes' values in ascending or descending order. Unlike arrays, linked lists do not support random access, so sorting must be done by rearranging the node links or values manually, not by indexing.