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 list2) ->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

## 0 Comments:

Post a Comment