Lecture Notes: Introduction to Linked Lists in C

Overview

• Basics of Linked Lists
  • What is a linked list?
  • Representation of a linked list
  • Singly linked lists
• Required Knowledge
  • Dynamic memory allocation
  • malloc function in C
  • Pointers
  • Structures in C
  • Accessing structure members

Logical View of Linked List

• A linked list consists of nodes.
• Example: A linked list with three nodes
  • Each node has two parts: Data part (holds actual data) and Address part (holds address of the next node).
  • Addresses are in hexadecimal form (for understanding purposes).
  • Last node’s address part contains zero (indicates end of the list).
• Head pointer: Stores the address of the first node.
  • Important to maintain in programs.

Creating a Node

• Use a user-defined data type (structure) to create a node.
• Structure definition: struct node { int data; struct node *next; };
• Structure is defined but not allocated memory yet.

Head Pointer

• Declaration: struct node *head; head = NULL; // Initially, the list is empty

Dynamic Memory Allocation

• Use malloc to allocate memory for nodes dynamically.
• Syntax: struct node *new_node; new_node = (struct node*) malloc(sizeof(struct node));
• Memory allocation details for a node:
  • Example: 8 bytes (4 for int data and 4 for pointer).

Inserting Data in a Node

• Using pointers to access structure members: scanf("%d", &new_node->data); // Insert data new_node->next = NULL; // Initially, next is NULL

Linking Nodes

• Maintaining Head Pointer and creating a list.
• Logic for inserting nodes:
  • If no nodes, head points to the new node.
  • If nodes exist, traverse to the last node and link new node.

Traversing the List

• Use a temp pointer to traverse (do not modify head).
• Print node data using traversal: temp = head; while(temp != NULL) { printf("%d ", temp->data); temp = temp->next; }

User Interaction for Continuation

• Ask user to continue or terminate node creation.
• Implementation using while loop: int choice = 1; while(choice) { // Code to create and link new node printf("Do you want to continue? (1/0)"); scanf("%d", &choice); }

Counting Nodes

• Use a counter variable to keep track of the number of nodes. int count = 0; temp = head; while(temp != NULL) { count++; temp = temp->next; } printf("Number of nodes: %d", count);

Summary

• Creating and linking nodes involves dynamic memory allocation and pointer manipulation.
• Traversing and displaying linked list elements requires careful maintenance of head and temporary pointers.
• User interactions and conditions to ensure proper list manipulation.

Next Steps

• Upcoming video: Insertion of nodes at beginning, specific positions, and end of the list.