Singly linked list

Singly linked list or One way chain

Singly linked list can be defined as the collection of ordered set of elements. The number of elements may vary according to need of the program. A node in the singly linked list consist of two parts: data part and link part. Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor.
One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each node contains only next pointer, therefore we can not traverse the list in the reverse direction.
Consider an example where the marks obtained by the student in three subjects are stored in a linked list as shown in the figure.
DS Singly Linked List
In the above figure, the arrow represents the links. The data part of every node contains the marks obtained by the student in the different subject. The last node in the list is identified by the null pointer which is present in the address part of the last node. We can have as many elements we require, in the data part of the list.

Complexity

Data StructureTime ComplexitySpace Compleity
AverageWorstWorst
AccessSearchInsertionDeletionAccessSearchInsertionDeletion
Singly Linked Listθ(n)θ(n)θ(1)θ(1)O(n)O(n)O(1)O(1)O(n)

Comments

Popular posts from this blog

Introduction of Digital computer

INTRODUCTION OF DBMS

Introduction to cache memory