What is Linked List in Data Structures?

A linked list, or one-way list, is a linear collection of data elements, called nodes, where the linear order is given by means of pointers. That is, each node is divided into two parts: the first part contains the information of the element, and the second part, called the link field or next pointer field, contains the address of the next node in the list.

Linked List Data Structures

Traversing a Linked list

Let LIST be a linked list in memory stored in linear arrays. INFO and LINK with START pointing to the first element and NULL indicating the end of LIST. Suppose we want to traverse LIST in order to process each node exactly once.

Algorithm: (Traversing a linked list.) TRVRS(INFO, LINK, START)

Let LINK be a linked list in memory. This algorithm traverses LIST, and prints the information at each node of a linked list. The variable PTR points to the node currently being processed.

Step I: Set PTR := START. [Initializes pointer PTR.]
Step II: Repeat steps 3 and 4 while PTR != NULL:
Step III: PRINT: INFO[PTR].
[Print information of node.]
Step IV: Set PTR := LINK[PTR].
[PTR now points to the next node.]
[End of step 2 loop.]
Step V: Exit.