© 2012 Firstsoft Technologies (P) Limited. login Hi 'Guest' Home SiteMap Contact Us Disclaimer
 Study Abroad Education Loan College News Placement Book Shops E - Books Engg-Admission Edu-Classifieds Students-Forum
Quick Links
Easy Studies
 « NS2  Projects »

Home Implementation Of Single Linked List▼

## Implementation Of Single Linked List:

Definition:

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

(or)

Linked list consists of series of nodes.Each node contains the element and a pointer to its successor node. The pointer of the last node points to NULL. Each record of a linked list is often called an element or node. The remaining fields may be called the data, information, value, or payload fields. The field of each node that contains address of the next node is usually called the next link or next pointer.

Types of Linked list:

1. Singly linked list.

2. Doubly linked list.

3. Circular linked list.

Advantages:

1. Length of the list need not be known in advance

2. Optimum use of memory

3. Insertion of element into the list is easier

4. Deletion of element from the list is easier

5. Concatenation of two linked lists is easier

6. Memory is not wasted if you remove an element from the list as it is freed

Singly linked list:

The simplest kind of linked list is a singly-linked list, which has one link per node. This link points to the next node in the list, or to a null value or empty list if it is the final node.

A singly linked list's node is divided into two parts. The first part holds or points to information about the node, and second part holds the address of next node. A singly linked list travels one way.

Operations on singly linked list:

1. Insert the element in the list.
2. Delete the element in the list
3.  Forward traverse.

Advantages of singly linked list:

1. Dynamic data structure.
2. We can perform deletion and insertion any where in the list.
3. We can merge two list easily.

Disadvantages of singly linked list:

1. Backward traversing is not possible in singly linked list.
2. Insertion is easy but deletion take some additional time, because disadvantage of backward traversing.

Algorithm steps:

Step1:     Create nodes first,last,next,prev and cur then set the value as NULL.

Step 2:    Read the list operation type.

step 3:    If operation type is create then  process the following steps.

1.  Allocate memory for node cur.

2.  Read data in cur's data area.

3.  Assign cur link as NULL.

4.  Assign first=last=cur.

Step 4:    If operation type is Insert then process the following steps.

1. Allocate memory for node cur.

2.  Read data in cur's data area.

3.  Read the position the Data to be insert.

4. Availability of the position is true then assing cur's link as first and   first=cur.

5.  If availability of position is false then do following steps.

1. Assign next as cur and count as zero.

2. Repeat the following steps until count less than postion.

1 .Assign prev as next

2. Next as prev of link.

3. Add count by one.

4. If prev as NULL then display the message INVALID POSITION.

5. If prev not qual to NULL then do the following steps.

1. Assign cur's link as prev's link.

2. Assign prev's link as cur.

Step5:  If operation type is delete then do the following steps.

1. Read the position .

2. Check list is Empty .If it is true display the message List empty.

3. If position is first.

1. Assign cur as first.

2. Assign First as first of link.

3. Reallocate the cur from  memory.

4. If position is last.

1. Move the current node to prev.

2.  cur's link as Null.

3. Reallocate the Last from memory.

4. Assign last as cur.

5.  If position is enter Mediate.

1. Move the cur to required postion.

2. Move the Previous to cur's previous position

3. Move the Next to cur's Next position.

4. Now Assign previous of link as next.

5. Reallocate the cur from memory.

step 6:  If operation is traverse.
1. Assign current as first.

2. Repeat the following steps untill cur becomes NULL.

C Program To Implement Single Linked List

CPP Program To Implement Single Linked List

⇓ Student Projects ⇓
⇑ Student Projects ⇑