Linked List vs Array | DSA in C++ - Software Development PDF Download

Introduction

Data structures play a crucial role in computer science and programming. When it comes to storing and manipulating data, two commonly used data structures are linked lists and arrays. In this article, we will explore the characteristics, advantages, and disadvantages of linked lists and arrays in the context of DSA (Data Structures and Algorithms) using C++.

Linked List

A linked list is a dynamic data structure where elements, called nodes, are connected through pointers. Each node contains a value and a pointer to the next node in the sequence. The last node points to NULL, indicating the end of the list.

Advantages of Linked List

Dynamic Size: Linked lists can grow or shrink dynamically during runtime, making them suitable for situations where the size of the data is unknown or frequently changing.

Insertion and Deletion: Insertion and deletion operations can be efficiently performed in a linked list by adjusting the pointers, without the need to shift elements as in arrays.

Memory Allocation: Linked lists allow efficient memory allocation since nodes can be dynamically created and deallocated as needed.

Disadvantages of Linked List

Random Access: Unlike arrays, linked lists do not support random access. To access an element, we need to traverse the list from the beginning, which can be time-consuming for large lists.

Extra Memory: Linked lists require additional memory to store the pointers, which can increase the overall memory consumption compared to arrays.

Sequential Access: Sequential access is faster in arrays due to their contiguous memory allocation, whereas linked lists suffer from cache misses when accessing elements in a non-sequential manner.

Example: Let's consider a simple example to demonstrate the use of a linked list in C++:

#include <iostream>

struct Node {

    int data;

    Node* next;

};

void printList(Node* head) {

    Node* current = head;

    while (current != nullptr) {

        std::cout << current->data << " ";

        current = current->next;

    }

    std::cout << std::endl;

}

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 = nullptr;

    printList(head);

    delete head;

    delete second;

    delete third;

    return 0;

}

Output:

1 2 3

Explanation:

In this example, we create a linked list with three nodes, where each node contains an integer value and a pointer to the next node. We then traverse the list and print its elements. Finally, we deallocate the memory allocated for the nodes using the 'delete' operator.

Array

An array is a static data structure that stores elements of the same type in contiguous memory locations. The elements can be accessed using their indices.

Advantages of Arrays

• Random Access: Arrays provide constant-time access to elements using their indices. This allows for efficient retrieval and modification of elements.
• Memory Efficiency: Arrays have a more memory-efficient representation than linked lists since they do not require extra pointers to maintain the connections between elements.
• Cache Locality: Arrays have better cache locality since the elements are stored in contiguous memory locations, leading to faster sequential access.

Disadvantages of Arrays

• Fixed Size: Arrays have a fixed size determined during their creation. Adding or removing elements may require resizing the array or creating a new one, which can be inefficient.
• Insertion and Deletion: Insertion and deletion operations in arrays involve shifting elements to accommodate the changes, which can be time-consuming for large arrays.
• Memory Waste: Arrays may waste memory if the allocated size is greater than the actual number of elements they hold.

Example:

Let's see an example of using arrays in C++:

#include <iostream>

int main() {

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

    std::cout << "Array elements: ";

    for (int i = 0; i < 5; i++) {

        std::cout << arr[i] << " ";

    }

    std::cout << std::endl;

    return 0;

}

Output:

Array elements: 1 2 3 4 5

Explanation:

In this example, we create an array 'arr' of size 5 and initialize it with some values. We then traverse the array using a loop and print its elements.

Sample Problems

Problem 1: Write a C++ program to find the length of a linked list.

#include <iostream>

struct Node {

    int data;

    Node* next;

};

int getLength(Node* head) {

    int length = 0;

    Node* current = head;

    while (current != nullptr) {

        length++;

        current = current->next;

    }

    return length;

}

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 = nullptr;

    int length = getLength(head);

    std::cout << "Length of the linked list: " << length << std::endl;

    delete head;

    delete second;

    delete third;

    return 0;

}

Output:

Length of the linked list: 3

Problem 2: Write a C++ program to find the sum of elements in an array.

#include <iostream>

int getArraySum(int arr[], int size) {

    int sum = 0;

    for (int i = 0; i < size; i++) {

        sum += arr[i];

    }

    return sum;

}

int main() {

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

    int size = sizeof(arr) / sizeof(arr[0]);

    int sum = getArraySum(arr, size);

    std::cout << "Sum of array elements: " << sum << std::endl;

    return 0;

}
Output:

Sum of array elements: 15

Conclusion

Both linked lists and arrays have their own advantages and disadvantages, and their suitability depends on the specific requirements of the problem at hand. Linked lists are beneficial for dynamic size and efficient insertion/deletion operations, while arrays provide random access and better memory efficiency. By understanding the characteristics and trade-offs of these data structures, you can make informed decisions in your DSA implementations using C++.