Linked List
Data Structure
Array Limitations
• Fixed size
• Physically stored in consecutive memory
locations, so to insert or delete items, may
need to shift data
Linked List Data Structures
• A linked data structure consists of
items that are linked to other items
• Each item points to another item
Memory
Addr 1 Addr 2 Addr 3
Addr 2 Addr 3 null
data1 data2 data3
Linked List Data Structures
• A linked data structure consists of
items that are linked to other items
• Each item points to another item
Memory
Addr 1 Addr 2 Addr 3
Addr 2 Addr 3 null
data1 data2 data3
Singly Linked Data Structures
• Singly linked list: each item points to the
next item
Memory
Addr 1 Addr 2 Addr 3
data1 data2 data2
Conceptual Diagram of a Singly-
Linked List
Front / Start / Header
4-6
Advantages of Linked Lists
• The items do not have to be stored in
consecutive memory locations, so we
can insert and delete items without
shifting data.
• Linked lists can grow and shrink
dynamically (i.e. at run time).
4-7
Nodes
• A linked list is an sequence of items called nodes
• A node in a singly linked list consists of two fields:
• A data / information portion
• A link (pointer) to the next node in the structure
• The first item (node) in the linked list is accessed via
a front or head or start pointer
Front / start / head
data next
4-8
Problem statement
• construct a singly linked list consisting of
the following information in each node:
• student regd_no (int)
• mark secured in a subject (float).
class Node {
• regd_no protected int regd_no;
• mark
next protected float mark;
protected Node next;
}
4-9
Linked List Operations
• Create a node - item of the linked list
• Add a node - item to the linked list
• insert at the front
• insert at the end
• insert at a specific position
• Delete a node - item from the linked list
• delete from the front
• delete from the end
• delete from a specific position
• delete based on the data/information 4-10
Linked List Operations cont…
• Search a node based on the data/information
• Sort the nodes based on the data/information
• Count the number of nodes
• Reverse the linked list
• Display all the nodes of the linked list
4-11
Linked List Key Operation
• Traversing the linked list
• How is the first item accessed?
– use start node
• What does the last item point to?
- the null link
4-12
Create a node
public static void create(Node start) {
System.out.print("Enter registration number: ");
start.regd_no = sc.nextInt();
System.out.print("Enter mark: ");
start.mark = sc.nextFloat();
start.next = null;
System.out.print("Add more nodes? (1 for Yes, 0 for No): ");
int choice = sc.nextInt();
Node current = start; start
while (choice == 1) {
current.next = new Node();
• regd_no
current = current.next;
System.out.print("Enter registration number: "); • mark
next
current.regd_no = sc.nextInt();
System.out.print("Enter mark: ");
current.mark = sc.nextFloat();
current.next = null;
System.out.print("Add more nodes? (1 for Yes, 0 for No): ");
choice = sc.nextInt();
}
}
4-13
Inserting a Node at the Front
New node
start (Existing
linked list)
1. Make the new node point to the
New node first node (i.e. the node that start
points to)
start
start New node 2. Make start point to the new node
4-14
Inserting a Node at the Front
public static Node InsBeg(Node start) {
Node newNode = new Node();
System.out.print("Enter registration number: ");
newNode.regd_no = sc.nextInt();
System.out.print("Enter mark: ");
newNode.mark = sc.nextFloat();
newNode.next = start;
System.out.println("Node inserted at beginning successfully!");
return newNode;
}
4-15
Inserting a Node at the End
1. Locate the last node New node
last
start
2. Make new node point to null New node
3. Make last point to new node
start New node
last
Inserting a Node at the End
public static Node InsEnd(Node start) {
Node newNode = new Node();
System.out.print("Enter registration number: ");
newNode.regd_no = sc.nextInt();
System.out.print("Enter mark: ");
newNode.mark = sc.nextFloat();
newNode.next = null;
if (start == null) {
System.out.println("Node inserted at end successfully!");
return newNode;
}
Node current = start;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
System.out.println("Node inserted at end successfully!");
return start; 4-17
}
Inserting a Node at a Specific Position
Let's insert the new node after the third New node
node in the linked list
start insertion point
1. Locate the node preceding the insertion point , since it will have to
be modified (make current point to it) node
New node
start
current
4-18
Inserting a Node at a Specific Position
2. Make the new node point to the node after the insertion point (i.e. the
node pointed to by the node that current points to)
New node
start
current
3. Make the node pointed to by current point to the new node
New node
start
current
4-19
Inserting a Node at a Specific Position
public static Node InsAny(Node start) {
System.out.print("Enter position to insert: ");
int pos = sc.nextInt();
if (pos < 1) {
System.out.println("Invalid position!");
return start;
}
if (pos == 1) {
return InsBeg(start);
} Node newNode = new Node();
System.out.print("Enter registration number: ");
newNode.regd_no = sc.nextInt();
System.out.print("Enter mark: ");
newNode.mark = sc.nextFloat();
Node current = start;
for (int i = 1; i < pos-1 && current != null; i++) {
current = current.next;
} if (current == null) {
System.out.println("Position out of range!");
return start;
} newNode.next = current.next;
current.next = newNode;
System.out.println("Node inserted at position " + pos + " successfully!");
return start; 4-20
}
Deleting a Node from the Front
start (Existing
linked list)
Node to be
deleted
Make start point to the next link of the
first node
start => Update start to start.next
4-21
Deleting a Node from the Front
public static Node DelBeg(Node start) {
if (start == null) {
System.out.println("List is empty!");
return null;
}
System.out.println("Node deleted from beginning successfully!");
return start.next;
}
4-22
Deleting a Node from the End
1. Locate the second last node
Second last node
start
2. Make its next to null
start
Deleting a Node from the End
public static Node DelEnd(Node start) {
if (start == null) {
System.out.println("List is empty!");
return null;
}
if (start.next == null) {
System.out.println("Node deleted from end successfully!");
return null;
}
Node current = start;
while (current.next.next != null) {
current = current.next;
}
current.next = null;
System.out.println("Node deleted from end successfully!");
return start;
}
4-24
Deleting a Node from a Specific Position
1. Locate the node preceding the deletion point , since it will have to
be modified (make current point to it)
Node preceding the
Node to be deleted
deletion point
start
2. Bypass the node to be deleted => update next of preceding node
to the next of node to be deleted
start
4-25
Deleting a Node from a Specific Position
public static Node DelAny(Node start) {
if (start == null) {
System.out.println("List is empty!");
return null;
}
System.out.print("Enter position to delete: ");
int pos = sc.nextInt();
if (pos < 1) {
System.out.println("Invalid position!");
return start;
}
if (pos == 1) {
return DelBeg(start); }
Node current = start;
for (int i = 1; i < pos-1 && current.next != null; i++) {
current = current.next;
}
if (current.next == null) {
System.out.println("Position out of range!");
return start;
}
current.next = current.next.next;
System.out.println("Node deleted from position " + pos );
return start; 4-26
}
