Back to course

Self-Referential Structures (Introduction to Linked Lists)

C Language: 0 to Hero - The Complete Beginner's Guide

Lesson 44: Self-Referential Structures (Introduction to Linked Lists)

A self-referential structure is a structure that contains at least one member that is a pointer to another structure of the same type.

These structures are the building blocks for dynamic data structures like Linked Lists, Trees, and Graphs.

Defining the Structure

The structure must include a data field and a pointer field.

c struct Node { int data; // Data stored in this node struct Node *next; // Pointer to the next node in the list };

Note: The structure cannot contain the structure itself as a member (e.g., struct Node n;) because that would require infinite memory. It must be a pointer to the structure type.

Linked List Concept

A Linked List is a sequence of nodes where each node is connected to the next via a pointer.

  1. A special pointer (head or start) points to the first node.
  2. Each node points to the next node.
  3. The pointer in the last node is set to NULL to signify the end of the list.

Example (Conceptual Linkage)

c struct Node *head, *node1, *node2;

// 1. Allocate memory for nodes node1 = (struct Node *)malloc(sizeof(struct Node)); node2 = (struct Node *)malloc(sizeof(struct Node));

// 2. Set data node1->data = 10; node2->data = 20;

// 3. Link them up node1->next = node2; node2->next = NULL; // End of list

head = node1; // Start here

We have created a list: HEAD -> [10 | addr_2] -> [20 | NULL].