Linked List

A linked list is a linear collection of data elements called nodes, where the linear order is given by the means of pointers.
The number of nodes on a list may vary dynamically as elements are inserted and removed.
The entire linked list is accessed from an external pointer list called start/first/head that points to the first node in the list.
A special case is the list that has no nodes, such a list is called null list or empty list and is denoted by a null pointer in the variable start/first/head.

Singly Linked List

Each node is divided into two parts.
The first part is the information part of the node, which contains data.
The second part called linked field or next pointer field, contains the address of the next node of the list.
The next address field of the last node in the list contains a special value, known as null, which is not a valid address.

It is similar to the singly linked list with a minor change in it.
The next address of the last node in the list contains the address of first node.
If we begin at a given node and traverse the entire list, we ultimately end up at the starting point.

A header linked list is a linked list which always contains a special node, called head node at the beginning of the list.
This special node in general used to store number of nodes present in the linked list or some other meta data.

The list which can be traversed in two directions: in the forward direction from the beginning of the list to the ends or in the backward direction from the end of the list to the beginning of the list.
Furthermore given the location of a node in the list, one now has immediate access to both the enxt node and the preceding node of the list.
This means in particular that one is able to delete a node from the list wothout traversing any part of the list.

Do not suffer from internal and external fragmentation.
A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Can easily support insertion or deletion.

It does not allow direct search, supports only sequential search even if linked list is sorted i.e., if we want to access a particular node then we have to start from the first node.
A good amount of space is wasted in storing pointers.

In linked list each node contains a minimum of two fields. One field is data field to store the data, second field is?

Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented in O(1) time?