C DSALesson 62Free preview

C Linked Lists

This lesson is part of C · All levels

Summary

Linked lists store data in nodes that are connected to each other via the next pointer, so that inserting and deleting in the middle is enough to break and connect the pointer without shifting other elements. Unlike arrays, linked lists do not support indexed random access and require separate memory allocation for each node. Types include singly linked list, doubly linked list, and circular linked list.

Key points

Each node contains data and pointers to the next node, and the head points to the first node.
The search is done with an auxiliary pointer such as current = current->next until it reaches NULL.
The insertion in the head takes place O(1), while the search for a particular position remains O(n).
Keep the pointer next node last always NULL so that the list does not intersect or rotate endlessly.
Disadvantages compared to arrays: there is no index and each node is located separately so it is not close to each other in memory.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.