Data Structures: Linked Lists

Introduction

• Previous Lecture: Covered basics of Linked Lists, need, benefits.
• Shared notes for the basic theory of Linked Lists.

Key Concepts of Linked Lists

• Memory Storage:
  • Arrays store elements in contiguous memory locations.
  • Linked Lists store elements in non-contiguous memory locations.
  • Each node contains data and a pointer to the next node.
  • The last node points to NULL.

Linked List Creation

• Elements of Linked List:
  • struct Node containing int data and struct Node *next.
  • Example Node creation: struct Node *head = (struct Node *)malloc(sizeof(struct Node));

Linked List Structure

• Nodes:
  • First node: head or Head Node.
  • Second node, third node, etc.
  • Last node points to NULL to denote the end.

Linked List Traversal

• Traversal Process:
  • Create a pointer ptr to the head node.
  • Move through the list node by node using ptr = ptr->next.
  • Stop when ptr becomes NULL.
  • Time Complexity: O(n) for n nodes.

Code Implementation

Struct Definition

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

Node Creation and Linking

• Creation and linking sample code:

struct Node *head = (struct Node *)malloc(sizeof(struct Node));
head->data = 7;
head->next = second; // Linking first and second
second->data = 11;
second->next = third; // Linking second and third
third->data = 66;
third->next = NULL; // Ending the list

Linked List Traversal Function

• Function Implementation:

void linkedlistTraversal(struct Node *ptr) {
    while (ptr != NULL) {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

Full Code Example

#include <stdio.h>
#include <stdlib.h>

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

void linkedlistTraversal(struct Node *ptr) {
    while (ptr != NULL) {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}

int main() {
    struct Node *head = (struct Node *)malloc(sizeof(struct Node));
    struct Node *second = (struct Node *)malloc(sizeof(struct Node));
    struct Node *third = (struct Node *)malloc(sizeof(struct Node));
    
    head->data = 7;
    head->next = second;

    second->data = 11;
    second->next = third;

    third->data = 66;
    third->next = NULL;

    linkedlistTraversal(head);
    return 0;
}

Additional Tips and Resources

• Dynamic Memory Allocation: Nodes are created in the heap.
• Importance of NULL: Marks the end of the linked list.
• Reference the C Language tutorial for deeper understanding, especially focusing on syntax and specific operations.
• Next Steps: Future lectures will cover more operations like insertion and deletion.

Conclusion

• Bookmark the playlist for future references.
• Share and tag for acknowledgement on social media.

Notes Access

• Make sure to access the shared notes and code for further study and clarity.