Lesson 2 - Arrays and Linked List

Array

is a collection of elements, each identified by an index or a key, stored in contiguous (adjacent) memory locations. All elements in an array must be of the same data type.

Array Index

Elements are accessed by their indexes.

Array Element

Items stored in an array.

Fixed size (for static arrays)

the size is declared at creation and generally

cannot be changed.

Homogeneous

all elements share the same data type.

Indexed access

each element has a unique index, typically starting at 0 (zero- based indexing).

Contiguous memory allocation

enables fast, direct (random) access to elements.

Fixed size, Homogeneous, Indexed access, Contiguous memory allocation

Key Characteristics of an Array

Constant Time Access

Direct access to any element using its index.

Easy Traversal

Simple to loop through all elements using a for loop.

Effective Data Storage

Useful for storing multiple values of the same type.

Constant Time Access,Easy Traversal,Effective Data Storage

Properties of Arrays

One dimensional array, two dimensional array, multi-dimensional array, static array, and dynamic array

Enumerate the types of array

One dimensional array

is a linear data structure that stores a collection of elements of the same data type in a single, contiguous block of memory. Each element is accessed using an index representing its position.

Two dimensional array

array is a collection of elements arranged in rows and columns, forming a matrix- like structure.

multi-dimensional array

Array with more than two-dimensions.

Static array

Fixed size determined at compile time.

Dynamic array

size can grow or shrink at runtime

traversal, insertion, searching, deletion, updating

Enumerate the types of array operations

Traversal

in an array refers to the process of accessing each element in the array sequentially, typically to perform a specific operation, such as searching, sorting, or modifying the elements.

Insertion

involves adding a new element to a specific position within an array.

Linked List

A linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers.

Node Structure

A node in a linked list typically consists of two components:

Data and Next pointer

Data

It holds the actual value associated with the node.

Next Pointer

It stores the memory address (reference) of the next node in the sequence.

Head and Tail

The linked list is accessed through the __ node, which points to the first node in the list. The last node in the list points to NULL or null pointer, indicating the end of the list. This node is known as the _ node.

Singly linked list, doubly linked list, circular linked list

Enumerate the types of linked list

Singly linked list

Each node contains a reference to the next node in the sequence. Traversing this linked list is done in a forward direction.

Doubly linked list

Each node contains references to both the next and previous nodes. This allows for traversal in both forward and backward directions, but it requires additional memory for the backward reference.

Circular linked list

The last node points back to the head node. It can be either singly or doubly linked.

insertion, deletion, searching and traversing

Enumerate the types of linked list operations

Dynamic size

Linked lists do not have a fixed size, so you can add or remove elements as needed, without having to worry about the size of the list. This makes linked lists a great choice when you need to work with a collection of items whose size can change dynamically.

Efficient Insertion and Deletion

Inserting or deleting elements in a linked list is fast and efficient, as you only need to modify the reference of the next node.

Easy to navigate

Linked lists can be easily traversed, making it easier to find specific elements or perform operations on the list.

Slow access time

Accessing elements in a linked list can be slow, as you need to traverse the linked list to find the element you are looking for.

Pointers

Linked lists are more complex to understand and use compared to arrays. This complexity can make linked lists more difficult to debug and maintain.

Higher overhead

Linked list requires extra memory to store the reference to the next node.

Cache inefficiency

In linked lists the memory is not contiguous. This means that when you traverse a linked list, you are not likely to get the data you need in the cache, leading to cache misses and slow performance.

Extra memory required

Linked lists require an extra pointer for each node, which takes up extra memory.

Static array

An array of fixed size.