Single Linked List

Single linked list: -

Single Linked list is a linear data structure. It is used as a fundamental data structure in computer programming. It contains a collection of nodes which are connected by only one pointer in one direction. Each node is having two parts the first part contains the data and second part contains the address of the next node. The first part is called data field or information field and the second part is called as link field or next address field.

The graphical representation of linked list is

Hear the pointer start always points to the first node of a list and the end node is represented by special value called NULL.

Need for linked representation :-

The following problem arises when it is implemented by using arrays

1. Wastage of storage

2. It is not possible to add or delete in the middle of a list with out rearrangement

3. It is not possible to extend the size of a list

To overcome all the above problem by implementing the list using linked representation. In linear lists insertion and deletion operations are inexpensive.

Operations applied on single linked list:

The basic types of operations applied on single linked list are

.

1. Inserting a new element at the given position

2. Delete the element from the given position

3. Find the length of the list

4. Read the list from left to right

5. Retrieve the ith element

6. Copy a list

7. Sort the elements in either ascending or descending order

8. Combine 2 or more list

Algorithm to add an element to an existing list:

It is possible to add an element to an existing list in three ways they are

1) Add at the front

2) Add at end of list

3) Add at position

Assumptions :

1) start is a pointer which always points to the first node of a list

2) ->next stands for next node address

Add at the front of a list

Step1: create a new node

Step2: newnode->next = start

Step3: start = newnode

Add at the end of a list

Step1: create a new node (newnode)

Step2: t = start

Step3: while (t->next != NULL ) t=t->next;

Step3: t->next = newnode

Add after a node of a list (position)

Step1: create a new node (newnode)

Step2: read the position of the node p;

Step3: t = start

Step4: traverse the list up to position as

for (i=1; inext;

Step4: newnode->next = t->next;

Step5: t->next = newnode

Algorithm for delete an element from the list

it is possible to delete an element from an existing list in three ways

· Delete at front

· Delete at end

· Delete at a position

Delete at front:

Step1: t1 = start

Step2: start = start->next

Step3: delete (t1)

Delete at end :

Step1: t = start;

Step2: traverse the list up to n-1 nodes as

For (I =1; I < t =" t-">next

Step3: t1= t->next;

Step4: t->next = t->next->next;

Step5: delete ( t1 )

Delete at position:

Step1: read the position of the deleted node p

Step2: traverse the list upto p-1as

For (i=1;inext;

Step3: t1 = t->next;

Step4: t->next= t->next->next

Step5: delete (t1)


delete a node at position 2

Drawbacks of a single linked list:

It is having only one pointer so that it is possible to traverse in only one way