Linked list
Another method is to store an individual list item in whatever location is available and link
the individual item into an ordered sequence using pointers.
An element of a list is called a node. A node can consist of several data items and a
pointer, which is a variable that stores the address of the node it points to.
A pointer that does not point at anything is called a null pointer. It is usually represented
by ∅. A variable that stores the address of the first element is called a start pointer.
Node: an element of a list
Pointer: a variable that stores the address of the node it points to
Null pointer: a pointer that does not point at anything
Start pointer: a variable that stores the address of the first element of a linked list
In Figure below, the data value in the node box represents the key field of that node. There
are likely to be many data items associated with each node. The arrows represent the
pointers. It does not show at which address a node is stored, so the diagram does not give
the value of the pointer, only where it conceptually links to.
A new node, A, is inserted at the beginning of the list. The content of startPointer is copied
into the new node's pointer field and star tpointer is set to point to the new node, A.
Conceptual diagram of adding a new node to the beginning of a linked list
1
In Figure below, a new node, P, is inserted at the end of the list. The pointer field of node
L points to the new node, P. The pointer field of the new node, P, contains the null
pointer.
Conceptual diagram of adding a new node to the end of a linked list
To delete the first node in the list, we copy the pointer field of the node to be deleted into
StartPointer.
To delete the last node in the list , we set the pointer field for the previous node to the
null pointer.
2
Sometimes the nodes are linked together in order of key field value to produce an ordered
linked list. This means a new node may need to be inserted or deleted from between two
existing nodes.
To insert a new node, C, between existing nodes, Band D, we copy the pointer field of node
B into the pointer field of the new node, C. We change the pointer field of node B to point
to the new node, C.
To delete a node, D, within the list, we copy the pointer field of the node to be deleted,
D, into the pointer field of node B.
Pseudo code for inserting data into a singly linked list
There are three common scenarios for insertion:
1. Inserting at the beginning
2. Inserting at the end
3. Inserting at a specific position
3
Pseudo Code: Singly Linked List Node Structure
Structure Node
Data: integer
Next: Node
End Structure
1. Insert at the Beginning
Procedure InsertAtBeginning(head, newData)
Create newNode
newNode.Data ← newData
newNode.Next ← head
head ← newNode
End Procedure
2. Insert at the End
Procedure InsertAtEnd(head, newData)
Create newNode
newNode.Data ← newData
newNode.Next ← NULL
If head = NULL Then
head ← newNode
Else
current ← head
While current.Next ≠ NULL
current ← current.Next
End While
current.Next ← newNode
End If
End Procedure
4
3. Insert at a Specific Position
Procedure InsertAtPosition(head, newData, position)
Create newNode
newNode.Data ← newData
If position = 1 Then
newNode.Next ← head
head ← newNode
Else
current ← head
count ← 1
While count < position - 1 AND current ≠ NULL
current ← current.Next
count ← count + 1
End While
If current = NULL Then
Output "Position out of bounds"
Else
newNode.Next ← current.Next
current.Next ← newNode
End If
End If
End Procedure
pseudo code for deleting a node from a singly linked list
Pseudo Code: Delete from Singly Linked List
Assume the linked list is made of nodes like:
Structure Node
Data: integer
Next: Node
End Structure
5
1. Delete from the Beginning
Procedure DeleteAtBeginning(head)
If head = NULL Then
Output "List is empty"
Else
temp ← head
head ← head.Next
Delete temp
End If
End Procedure
2. Delete from the End
Procedure DeleteAtEnd(head)
If head = NULL Then
Output "List is empty"
Else If head.Next = NULL Then
Delete head
head ← NULL
Else
current ← head
While current.Next.Next ≠ NULL
current ← current.Next
End While
Delete current.Next
current.Next ← NULL
End If
End Procedure
6
3. Delete at a Specific Position
Procedure DeleteAtPosition(head, position)
If head = NULL Then
Output "List is empty"
Else If position = 1 Then
temp ← head
head ← head.Next
Delete temp
Else
current ← head
count ← 1
While count < position - 1 AND current.Next ≠ NULL
current ← current.Next
count ← count + 1
End While
If current.Next = NULL Then
Output "Position out of bounds"
Else
temp ← current.Next
current.Next ← temp.Next
Delete temp
End If
End If
End Procedure
