new 5: operations on single linked list (insertion and deletion)

Operations on Singly (Simply) Linked Lists
AddFirst
The insertFirst() method of LinkList inserts a new link at the beginning of the list. To insert the new link, we need only set the next field in the newly created link to point to the old first link and then change first so it points to the newly created link. This situation is shown in Figure below. The insertion it can be done in the following steps:
? create a new node.
Read v
P = new link (v, null)
? Update the next link of a new node, to point to the current head node.
p.next = head
? Update head link to point to the new node (i.e. make the new node to be the first node).
head = p
you can summarize the previous three steps in one statement as:
head = new link (v, head)
College of Information Technology / Software Department
………………………………………………………..
Data Structures / Second Class / 2017-2018
LEC. 4
20
Addlast
It can be done in the following steps:
? Create a new node.
? Set the next link of a new node to null.
? Access to the last node of linked list (it is pointed by tail).
? Update the next link of the current tail node, to point to the new node.
? Update tail link to point to the new node(make the new last node pointed by tail).
Read v
P = new link (v, null)
Tail = head
While Tail.next != null
Tail = Tail.next
Tail.next = p
Tail = p
21
Inserted Between Two Nodes
Such an insert can be done in the following steps:
? Determine the position of insertion.
Read pos
If pos >=1 and pos <= n+1
If pos = = 1
call addfirst // make a new node is the first node.
Else
If pos = = n+1
call addlast // make a new node is the last node.
Else
? Create a new node.
Read v
node = new link (v, null)
? Access to the node which is previous to the insertion position (it is pointed by p).
P = head
For i = 1 to pos-2
P = p.next
? Update link of the node, to point where the p.next points
node.next = p.next
? Update link of the "previous" node, to point to the new node
p.next = node