Linked List

Linked list is a dynamic data structure where memory is allocated non-contiguously. Each data item is linked with another data item using pointers. The terms used in linked list are

1. head: The pointer used to indicate the address of first data item.
2. data: The element placed at an address.
3. next: The pointer which refers the address of next data item.
4. node: The combination of data and next is called as node.

There are different types of linked lists. They are

1. Singly Linked List: The linking of data items moves only in forward direction i.e. only one pointer(next) is used in each and every node.
2. Doubly Linked List: The linking of the data items moves both in forward and backward i.e. two pointers (prev and next) are used in each node.
3. Circular Linked List: It is just like double linked list but the next address of last data item indicates first element address and prev of 1st data item refers to the last data item’s address.

Basic operations on Linked Lists:

1. Insertion: It concatenates an element to the linked list.
2. Deletion: Remove a data item from the linked list.
3. Search: It finds a n element in the linked list.
4. Traversal: It displays all the data items stored in a linked list.

Singly Linked List:

The linked list having only 1 pointer which refers the address of next data item is called Singly Linked List.

Singly Linked list representation:

Once when we move forward ,it is very hard to come back or we should traverse from the beginning.

Insertion:

The address of new data item is assigned to next part of the last data item.

Deletion:

Nullifying the next address of the last but one data item.

Search:

It starts from head to last data item by comparing data item with the key, if it matches ,it returns success else -1.

Traversal:

It displays all the elements in the linked list.

Programs on Singly linked list in c and java

C:

Java:

Sorting is very difficult in linked list.

In the next story , we will see about double linked list.

Thank you.