Arrays and Linked Lists

Arrays and Linked Lists

Arrays and linked lists are fundamental linear data structures. Understanding their operations and time complexities is crucial for GATE CS.

Arrays

Array is a collection of elements stored in contiguous memory locations.

Array Operations

Time Complexities:

• Access: O(1) - Direct access using index
• Search: O(n) - May need to check all elements
• Insert at end: O(1) - If space available
• Insert at position: O(n) - Need to shift elements
• Delete: O(n) - Need to shift elements

Space Complexity: O(n)

Array Implementation

Declaration:

int arr[10];           // Static array
int *arr = malloc(n * sizeof(int));  // Dynamic array

Access:

arr[i] = value;        // Write
value = arr[i];        // Read

Multi-dimensional Arrays

2D Array:

int matrix[3][4];      // 3 rows, 4 columns
matrix[i][j] = value;  // Access element

Memory Layout:

• Row-major: Elements stored row by row
• Column-major: Elements stored column by column

Address Calculation (Row-major):

• For array A[m][n], address of A[i][j] = Base + (i × n + j) × size

String Operations

String is an array of characters.

Common Operations:

• Length: O(n)
• Concatenation: O(n)
• Comparison: O(n)
• Substring: O(n)

Linked Lists

Linked List is a collection of nodes where each node contains data and a pointer to the next node.

Types of Linked Lists

1. Singly Linked List

Each node points to next node only.

Structure:

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

Operations:

• Insert at head: O(1)
• Insert at tail: O(1) with tail pointer, O(n) without
• Insert at position: O(n) - Need to traverse
• Delete: O(1) if position known, O(n) to find
• Search: O(n)
• Access: O(n)

2. Doubly Linked List

Each node points to both next and previous nodes.

Structure:

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

Advantages:

• Can traverse in both directions
• Easier deletion (don't need previous node pointer)

Disadvantages:

• Extra memory for previous pointer
• More complex operations

3. Circular Linked List

Last node points back to first node.

Advantages:

• Can start from any node
• Useful for round-robin scheduling

Linked List Operations

Insertion

Insert at Head:

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

Insert at Tail:

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

Insert at Position:

void insertAtPosition(Node** head, int data, int pos) {
    Node* newNode = createNode(data);
    if (pos == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    Node* temp = *head;
    for (int i = 0; i < pos - 1 && temp != NULL; i++)
        temp = temp->next;
    if (temp != NULL) {
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

Deletion

Delete by Value:

void deleteByValue(Node** head, int data) {
    if (*head == NULL) return;
    
    if ((*head)->data == data) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    
    Node* temp = *head;
    while (temp->next != NULL && temp->next->data != data)
        temp = temp->next;
    
    if (temp->next != NULL) {
        Node* toDelete = temp->next;
        temp->next = temp->next->next;
        free(toDelete);
    }
}

Array vs Linked List

GATE CS Important Points

1. Time Complexities: Know all operation complexities
2. Memory Layout: Understand array memory organization
3. Pointer Operations: Master linked list pointer manipulation
4. Insertion/Deletion: Practice all variations
5. Cycle Detection: Know Floyd's cycle detection algorithm

Practice Tips

1. Implement Operations: Code all operations from scratch
2. Trace Execution: Manually trace pointer operations
3. Handle Edge Cases: Empty list, single node, etc.
4. Memory Management: Understand malloc/free
5. Previous Year Questions: Solve GATE array/linked list questions