 # Data Structure : Linked list

Overview :
Linked List is a linear data structure .It is a collection of nodes.The nodes connect by pointer. Each node is contain two parts. data part, link part

• Data contains the node value. • Dynamic in nature
• Insertion and deletion can be easily implemented.
• Reduces the access time.

Single linked list contain nodes which have a data part as well as address part which points to the next node in sequence of nodes. Before being single linked list operation we need to d

• Random access is not allowed.
• Memory is wastage.
• Reverse traversing is difficult.

• It is used to implement stack , queue, , graph etc.
• Representing sparse matrix.
• For separate chaining hash-table.

There are three types of linked list

Single linked list contain nodes which have a data part as well as adress part which points to the next node in sequence of nodes.

Before doing Singly Linked operations we need to define structure for Single linked list.

``````struct node
{
int data;
node *next;
}*start=NULL:
``````

Node Creation :
Algorithm : creation(data)

```Step 1: Start
Step 2: Set temp = new node
Step 3: Set temp.data = data
Step 4: Set temp.next = NULL
Step 5: Return temp
Step 6: ENd
```

Traverse :
Algorithm: Traverse()

```Step 1: Start
Step 2: Set temp = start
Step 3: while(temp!=NULL)
print temp.data
temp = temp.next
Step 4: End
```

Insertion :

Insertion at First

```Algorithm : InserFirst( data)
Step 1: Start
Step 2: Set newn = creation(data).
Step 3: if(start==NULL) { start  = newn; start.next = NULL; }
else            { newn.next = start; start = newn; }
Step 4: End.
```

Insertion at Middle
Algorithm : InsertMiddle(data,position)

```Step 1: Start
Step 2: Set temp = start and newn = creation(data)
Step 3: for i=0 to position-2
temp = temp.next
Step 4: Set temp1 = temp.next
Step 5: temp.next = newn
Step 6: newn.next = temp1
Step 7: End.
```

Deletion:

```Algorithm : Delete(position)
Step 1: Start
Step 2: Set temp = start
Step 3: if(position==1)
{
if(start==NULL) print deletion not possible.
else            start = start.next; free(temp);
}

else
{
for i=0 to position-2
{
temp = temp.next;
}
Set temp1  = temp.next;
temp.next = temp1.next
free(temp1)
}

Step 4: End
```

Searching

```Algorithm :
Search(data)
Step 1 : Start
Step 2 : Set temp = start, position = 0, flag = false.
Step 3 : While (temp.next!=NULL)
position increment;
if(temp.data==data)
{
flag = true.
print data is found
break while loop;
}
temp = temp->next;