Fundamental Data Structures Lesson 2: Part 1

Array

A collection of items of same data type stored at contiguous memory locations

Array Index

In an array, elements are identified by their indexes.

Array Element

Items stored in an array and can be accessed by their index.

Array Length

The length of an array is determined by the number of elements it can contain.

One dimensional array, two dimensional array, three dimensional array

Enumerate the types of array

One dimensional array

A row, where elements are stored one after another.

Two dimensional array

Can be considered as an array of arrays or as a matrix consisting of rows and columns.

Three dimensional array

It can be considered an array of two-dimensional arrays.

traversal, insertion, searching, deletion, sorting

Enumerate the types of array operations

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.

Memory Efficiency

Linked lists use only as much memory as they need, so they are more efficient with memory compared to arrays, which have a fixed size and can waste memory if not all elements are used.

Easy to Implement

Linked lists are relatively simple to implement and understand compared to other data structures like trees and graphs.

Flexibility

Linked lists can be used to implement various abstract data types, such as stacks, queues, and associative arrays.

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.