Rauf

AI and ML

Introduction to Data Structures

Arrays and Linked Lists

Array

An array is a collection of elements (usually of the same type) that are stored contiguously in memory. Arrays provide fast access but have a fixed size. For example, if you declare an array of integers like int arr[100];, the size is fixed to 100 elements.

In an array, elements such as integers, floats, or strings are stored in contiguous memory locations. For instance, if the first element is stored at memory address 1X123, the next element will be at 1X124, and so on. This allows fast access, but the size is fixed once declared.

Array Example

Array example

In the above image, you can see how an array looks in memory. Each box represents an element, and the values (1, 2, 3, 4, 5) are stored in contiguous memory locations. The last box contains a null to signify the end of the array. Below each box, you can see memory addresses like 1X123, 1X124, etc.

Array Code

Array code

Here’s an example of an array in C++:

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    for(int i = 0; i < 5; i++) {
        cout << "Location: " << &arr[i] << " Value: " << arr[i] << endl;
    }

    cout << "Size of array: " << sizeof(arr) << endl;
    cout << "Size of element: " << sizeof(arr[0]) << endl;
    cout << "Length of array: " << sizeof(arr) / sizeof(arr[0]) << endl;
    cout << "arr[6]: " << arr[6] << endl;
    cout << "Location of arr[6]: " << &arr[6] << endl;

}

This code creates an integer array of size 5 and prints the memory locations and values of each element. The sizeof() function is used to determine the size of the array, the size of an element, and the length of the array. Note that arrays in C++ don't have a built-in length() function, unlike Python.

Linked List

Linked list

A linked list is different from an array in that it does not use contiguous memory. Instead, each element (or "node") contains a value and a reference (or pointer) to the next node in the list. Linked lists solve the problem of arrays, where memory must be contiguous. They are dynamic in size and can grow or shrink as needed.

Linked List Example

Linked list example

In this example, you can see how a linked list works. Each node contains data and a pointer to the next node. The last node points to null to indicate the end of the list.

Linked List Code

Linked list code

Here’s the code for a simple linked list implementation in C++:

struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = new Node();
    Node* second = new Node();
    Node* third = new Node();

    head->data = 1;
    head->next = second;
    second->data = 2;
    second->next = third;
    third->data = 3;
    third->next = NULL;

    Node* t = head;
    while (t != NULL) {
        cout << "Location: " << t << " Value: " << t->data << " Next: " << t->next << endl;
        t = t->next;
    }
}

In this code, a simple linked list is created. Each node points to the next node and contains data as an integer. The head node points to the second node, which in turn points to the third node. The list terminates with a NULL pointer.

Doubly Linked List

Doubly linked list

In a doubly linked list, we simply add another pointer in each node that points to the previous node. We then adjust the functions accordingly, and while assigning the next node, we also assign the previous node. It's a straightforward modification.

This concludes the tutorial. See you in the next one 😊

Check out the full video tutorial:

Arrays and linked list