Singly link list

only singly link list

1. Singly Lists –Linked List
Representation

2. Outlines
Singly link list
2

3. Definition
Singly list :-is a linear data structure .it
is linearly connected .It contains node
s. Each node contains two parts, i.e. D
ATA part and LINK part.
The data contains elements and
Link contains address of another node.
3

4. linkdata
A B C D
x
linklink linkData datadata
start
-START is List pointer contains address of the first node in
the List
-All nodes are connected to each other through Link fields
-Link of the last node is NULL pointer denoted by ‘X’ sign
-Null pointer indicated end of the list

5. Algorithms
 Lets consider,
•START is the 1
st
position in Linked List
•NewNode is the new node to be created
•DATA is the element to be inserted in new node
•POS is the position where the new node to be inserted
•TEMP and HOLD are temporary pointers to hold the nod
e address

6. Algorithm/c to Insert a Node at the beginning
1. Input DATA to be inserted
2. Create NewNode
3. NewNode -> DATA = DATA
4. If START is equal to NULL
 NewNode -> LINK = NULL
5. Else
 NewNode -> LINK = START
6. START = NewNode
7. Exit

7. Insert a Node at the beginning
x
linklink linkdatadatadata
start
NewNode

8. Algorithm/c to Insert a Node at the end
1.Input DATA to be inserted
2.Create NewNode
3.NewNode -> DATA = DATA
4.NewNode -> LINK = NULL
5.If START is equal to NULL
 a) START = NewNode
6. Else
 a) TEMP = START
 b) while (TEMP -> LINK not equal to NU
LL)
 i) TEMP = TEMP -> LINK
7. TEMP -> Link = NewNode
8.Exit

9. Insert a Node at the end
linkdata
A B C
linklink datadata
start
P
X
NewNode

10. 10
Algorithm/c to Insert a Node at any specified position
1.Input DATA to be inserted and POS, the position to be in
serted.
2.Initialize TEMP = START and K=1
3.Repeat step 3 while ( K is less than POS)
 TEMP = TEMP -> LINK
 If TEMP -> LINK = NULL
 i) Exit
 K = K + 1
4. Create a Newnode
5. Newnode -> DATA = DATA
6. Newnode -> LINK = TEMP -> LINK
7. TEMP -> LINK = NewNode
8. Exit

11. 11
Insert a Node at middle position
P
linkdata
A B
C
D
x
linklink linkdatadatadata
start
NewNode
4321
Lets consider, POS = 3

12. 12
Algorithm/c to Delete a Node
 1. Input DATA to be deleted
 2. If START is equal to DATA
 TEMP = START
 START = START -> LINK
 Set free node TEMP -which is deleted
 d) Exit
 3. HOLD = START
 4. While ((HOLD -> LINK ->LINK) not equal to NULL)
 a) If(HOLD -> LINK ->DATA) equal to DATA
 i) TEMP = HOLD -> LINK
 ii) HOLD -> LINK = TEMP -> LINK
 iii) Set free node TEMP -which is delete
d
 iv) Exit
 b) HOLD = HOLD -> NEXT

13. 13
Algorithm to Delete a Node
 5. If(HOLD -> LINK ->DATA) equal to DATA
 i) TEMP = HOLD -> LINK
 ii) Set free node TEMP -which is deleted
 iii) HOLD -> LINK = NULL
 iv) Exit
 6. Display DATA not found
 7. Exit

14. 14
Algorithm to Delete a Node
linkdata
A B C D
x
linklink linkdatadatadata
Node to be deleted
start

15. 15
Single linked List Properties
Stores a collection of items non-contiguously.
Each item in the list is stored with an indication of
where the next item is.
Must know where firstitem is.
The list will be a chain of objects, called nodes, of
type Nodethat containthe dataand a referenceto
the nextNodein the list.
Allows addition or deletion of items in the middle of
collection with only a constantamount of data mov
ement. Contrast this with array.
15