Problem Solving Through C Unit 10 Self Referential Structures and Linked Lists Notes Set 01

Advanced Study Material for Computer Science: Programming in C

Explore structured advanced study materials through the Problem Solving Through C Unit 10 Self Referential Structures and Linked Lists Notes Set 01. Tailored for learners, utilizing these Computer Science resources ensures thorough preparation and strengthens foundational knowledge before final evaluations.

Practice Computer Science Resources: Programming in C

View or download the dedicated Problem Solving Through C Unit 10 Self Referential Structures and Linked Lists Notes Set 01 resource below. Engaging with these advanced study guides under focused conditions ensures continuous academic progress and mastery of the 2026-27 curriculum for Programming in C.

This page introduces self-referential structures and singly linked lists in C: how a node holds data and a next pointer, the role of the head pointer, traversal, and the steps and code for inserting a node at the beginning, end or middle and for deleting the first, last or any other node.

Self-referential Structures

  • A structure can have members which point to a structure variable of the same type.
  • These types of structures are called self-referential structures and are widely used in dynamic data structures like trees, linked list, etc.
  • The following is a definition of a self-referential structure.
struct node
{
    int data;
    struct node *next;
};
  • Here, next is a pointer to a struct node variable.
  • It should be remembered that a pointer to a structure is similar to a pointer to any other variable.
  • A self-referential data structure is essentially a structure definition which includes at least one member that is a pointer to the structure of its own kind.
  • A chain of such structures can thus be expressed as follows.
struct name
{
    member 1;
    member 2;
    ...
    struct name *pointer;
};
  • The above illustrated structure prototype describes one node that comprises of two logical segments.
  • One of them stores data/information and the other one is a pointer indicating where the next component can be found.
  • Several such inter-connected nodes create a chain of structures.
  • The following figure depicts the composition of such a node: a node is a box with a data part followed by a pointer part, and the pointer part leads to the next node.
  • The figure is a simplified illustration of nodes that collectively form a chain of structures or linked list.
  • Such self-referential structures are very useful in applications that involve linked data structures, such as lists and trees.
  • Unlike a static data structure such as array where the number of elements that can be inserted in the array is limited by the size of the array, a self-referential structure can dynamically be expanded or contracted.
  • Operations like insertion or deletion of nodes in a self-referential structure involve simple and straight forward alteration of pointers.

Linked Lists

  • A linked list is a useful method of data storage that can easily be implemented in C.
  • There are several kinds of linked lists, including single-linked lists, double-linked lists, and binary trees.
  • Each type is suited for certain types of data storage.
  • The one thing that these lists have in common is that the links between data items are defined by information that is contained in the items themselves, in the form of pointers.
  • This is distinctly different from arrays, in which the links between data items result from the layout and storage of the array.

Creation of a Singly Connected Linked List

Figure description (Singly Linked List): the head points to the first node. Each node has a data part and an address part; the last (tail) node holds NULL in its address part. The nodes of the figure are:

Node addressDataNext
1006300
3009400
40012200
2005700
700-10NULL

Basics of Linked Lists

  • Each data item in a linked list is contained in a structure.
  • The structure contains the data elements needed to hold the data being stored; these depend on the needs of the specific program.
  • In addition, there is one more data element--a pointer.
  • This pointer produces the links in a linked list. Here's a simple example:
struct person
{
char name[20];
struct person *next;
};
  • This code defines a structure named person.
  • For the data, person contains only a 20-element array of characters.
  • One generally wouldn't use a linked list for such simple data, but this will serve as an example.
  • The person structure also contains a pointer to type person--in other words, a pointer to another structure of the same type.
  • This means that each structure of type person can not only contain a chunk of data, but also can point to another person structure.

Head Pointer

  • This is identified by a special pointer (not a structure) called the head pointer.
  • The head pointer always points to the first element in the linked list.
  • The first element contains a pointer to the second element; the second element contains a pointer to the third, and so on until one encounters an element whose pointer is NULL.
  • If the entire list is empty (contains no links), the head pointer is set to NULL.
  • NOTE: The head pointer is a pointer to the first element in a linked list.
  • The head pointer is sometimes referred to as the first element pointer or top pointer.

Self-Referential Structures and Linked Lists - Head and Tail

Figure (a list holding 2, 4, 6 and 8; the last node's pointer is NULL and the tail points to the last node):

head --> [ 2 | * ] --> [ 4 | * ] --> [ 6 | * ] --> [ 8 | NULL ]
                                              ^
                                             tail

Traversing Linked List

  • A linked list is a data structure that is used to model such a dynamic list of data items, so the study of the linked lists as one of the data structures is important.
  • Linked list is essentially an ordered list of some data in which one can traverse it (examine it) in only one direction.
  • Linked list is made up of nodes that consist of data section that holds the actual data and a link section, which contains information about the next node in the list.
  • Usually, that link section contains a pointer to the next node, or in array implementation of the list, an index of the next node.
  • Usually Linked List has the following functions:
    1. Add - adds an element at the end of the list.
    2. Add (position) - adds an element at a certain position.
    3. Remove (position) - removes a certain element.
    4. Traverse - traverses the list and possibly display its content on the screen.
    5. IsEmpty - function that checks if the list is empty or not and possibly others such as getSize, etc.
  • It is important to check the position parameter when Add (position) and Remove (position) functions are called.
  • Suppose the list has 5 elements in total - 0 to 4.
  • It would be legal to call Add or Remove with position parameter in the range of 0 to 4 and also it would be legal to call Add with the position parameter value of 5, which would essentially add a new Node at the very end of the list (after the 4th element).
  • Thus in a linked list of 4 elements Node 0 has a pointer to Node 1, Node 1 to Node 2, Node 2 to Node 3.
  • Also need to keep a pointer to the first node in the list, First Node (which is Node 0 in the above example) to be able to access the list at all.
  • Clearly, next is used to create a link to the next node in the list, hence the name linked list.
  • Linked list can be represented graphically as: First Node --> Node 0 --> Node 1 --> Node 2 --> Node 3 --> nothing.

Steps for Traversing the linked list:

1. Start at the beginning - First Node.
2. Access node's data section.
3. Print out the data or does some other work per application specification.
4. Access the next node by using the link provided in the next section of the current node. Repeat step 2.

Do steps 2 and 3 as long as the last node is not reached. Last node will point to nothing in its next section. Nothing is represented variously depending on the actual implementation.

Insertion into a Linked List

Adding an Element to the Beginning of a List

  • If the head pointer is NULL, the list is empty, and the new element will be its only member.
  • If the head pointer is not NULL, the list already contains one or more elements.
  • In either case, however, the procedure for adding a new element to the start of the list is the same:

1. Create an instance of the structure, allocating memory space using malloc().
2. Set the next pointer of the new element to the current value of the head pointer. This will be NULL if the list is empty, or the address of the current first element otherwise.
3. Make the head pointer point to the new element.

Here is the code to perform this task:

new=(person*)malloc(sizeof(struct person));
new->next=head;
head=new;

Adding an Element to the Beginning of a List: Example

Figure description: a list 44, 32, 67, 18, 53 with the head at 44 and the tail at 53; the new element is linked in front of 44 and the head (first) pointer is moved to it.

Adding an Element to the Beginning of a doubly Linked List: Example

Figure description: a doubly linked list holding 55, 78, 48, 3 (with addresses 200, 100, 400, 500) where p points to the first node; temp points to a new node at address 700 whose data part is set to 999 using temp.

WARNING:

  • It is important to switch the pointers in the correct order.
  • If one re-assigns the head pointer first, one will lose the list.
  • The malloc() is used to allocate the memory for the new element.
  • As each new element is added, only the memory needed for it is allocated.
  • The calloc() function could also be used.
  • One should be aware of the differences between these two functions.
  • The main difference is that calloc() will initialize the new element; malloc() will not.

Adding an Element to the End of the List

1. To add an element to the end of a linked list, one needs to start at the head pointer and go through the list until one finds the last element.
2. Create an instance of the structure, allocating memory space using malloc().
3. Set the next pointer in the last element to point to the new element (whose address is returned by malloc()).
4. Set the next pointer in the new element to NULL to signal that it is the last item in the list.

Here is the code:

person *current;
...
current=head;
while(current->next!=NULL)
    current=current->next;
new=(person*)malloc(sizeof(struct person));
current->next=new;
new->next=NULL;

Example: a doubly linked list holding 14, 30, 25, 42, 9 (addresses 200, 100, 400, 500, 700) where p points to the first node, temp to the node 42 and r to the last node 9.

Adding an Element to the End of the singly linked list: Example: a list 32, 67, 18, 53, 67 with the head at 32; first points to the head and last points to the final node, whose next pointer is NULL.

Adding an Element to the End of a doubly Linked List Example: a doubly linked list holding 55, 78, 48, 3, 99 where p points to the first node, temp to the node 3 and r to the last node 99.

Adding an Element to the Middle of the List

1. When one is working with a linked list, most of the time one will be adding elements somewhere in the middle of the list. Exactly where the new element is placed depends on how one keeps the list--for example, if it is sorted on one or more data elements. This process, then, requires that one first locates the position in the list where the new element will go, and then add it.
2. In the list, locate the existing element that the new element will be placed after. Let's call this the marker element.
3. Create an instance of the structure, allocating memory space using malloc().
4. Set the next pointer of the new element to point to the element that the marker element used to point to.
5. Set the next pointer of the marker element to point to the new element (whose address is returned by malloc()).

Here's how the code might look:

person *marker;
/* Code here to set marker to point to the desired list location. */
...
new=(LINK)malloc(sizeof(PERSON));
new->next = marker->next;
marker->next = new;

Example: after insertion in a singly linked list, the list reads 14, 30, 3, 99, 9, 17 (addresses 200, 100, 400, 700, 500, 300) with p at the first node, temp at the node 3 and r at the node 99.

Deletion from a Linked List

  • Deleting an element from a linked list is a simple matter of manipulating pointers.
  • The exact process depends on where in the list the element is located:
    1. To delete the first element, set the head pointer to point to the second element in the list.
    2. To delete the last element, set the next pointer of the next-to-last element to NULL.
    3. To delete any other element, set the next pointer of the element before the one being deleted to point to the element after the one being deleted.
  • Here's the code to delete the first element in a linked list: head = head->next;

Example

Deletion of a node from a linked list: a list 7, 89, 12, 71 (addresses 200, 100, 400, 300).

Deleting an element from the list: a list 67, 18, 53 with the head at 67 and the tail at 53.

The following are the codes to delete the last element and the element in the middle of the list:

person *current1, *current2;

current1=head;
current2=current1->next;
while(current2->next!=NULL)
{
    current1=current2;
    current2=current1->next;
}
current1->next=NULL;
if(head==current1)
    head=NULL;

Deleting from the middle of a list: a list 32, 67, 53 where prev points to the node 67.

The following code deletes an element from within the list:

person *current1, *current2;

/* Code goes here to have current1 point to the
   Element just before the one to be deleted*/

current2=current1->next;

current1->next=current2->next;
  • After any of these procedures, the deleted element still exists in memory, but it is removed from the list because there is no pointer in the list pointing to it.
  • The memory occupied by it is released with the free() function.

Useful Resources and Notes for Computer Science Programming in C

Quick Revision Material for Programming in C

Access comprehensive study material for Programming in C, including revision notes, concept maps, and high-probability questions. These resources are designed in alignment with the latest 2026 CBSE syllabus for Computer Science to support effective exam preparation.

Expert Notes and Solved Exam Questions

Built using official NCERT guidelines for Computer Science, these materials provide reliable academic support. Integrating past examination questions and step-by-step solutions helps students understand official CBSE grading criteria.

Additional Study Resources for

Wrap up your chapter revision by testing your knowledge against standard objective question formats. Explore our full library of free, up-to-date sample papers and online assessments to secure top grades in your CBSE examinations.

FAQs

Where can I find the most advanced study material for [current-page:node:field_board] [current-page:node:field_class] Computer Science for 2026-27?

The latest 2026-27 advanced study resources for Computer Science are available for free on StudiesToday.com which includes NCERT Exemplars, high-order thinking skills (HOTS) questions, and deep-dive concept summaries.

What does the 2026-27 Computer Science study package for [current-page:node:field_class] include?

Our exhaustive Computer Science package includes chapter wise revision notes, solved practice sheets, important formulas and Concept Maps to help in better understanding of all topics.

Is this study material enough for both [current-page:node:field_board] exams and competitive tests?

Yes. For , our resources have been developed to help you get better marks in school exams and also build fundamental strength needed for entrance tests including Competency Based learning.

How should [current-page:node:field_class] students use this Computer Science material for maximum marks?

in , students should use Active Recall method, read the concept summary, then solve the Important Questions section without looking at the answers and then check your answers.

Can I download [current-page:node:field_class] Computer Science study notes in PDF for offline use?

All Computer Science study materials are provided in mobile-friendly PDF. You can download and save them on your device.

Are the [current-page:node:field_class] Computer Science resources updated for the latest NEP guidelines?

Yes, our team has ensured that all Computer Science materials for are strictly aligned with the National Education Policy (NEP) 2020 and the latest 2026-27 syllabus.