CSC 220

Data Structures and Algorithms

Lecture # 9

Linked Lists
Lecture Outlines 2

Lecture Outlines
• Singly Linked List
 Linked List and Array
 Linked List Terms
 Linked List Design
 Adding a New Node
 Printing a Linked List
 Inserting a Node
 Removing a Node
 Limitations of Singly Linked List
Lecture Outlines 3

Lecture Outlines (cont.)

• Doubly Linked List
 Node Class in a Doubly Linked List
 Inserting a Node
 Removing a Node
 Printing a Doubly Linked List

• The Circularly Linked List

Linked List (Singly Linked List) 5

Linked List (Singly Linked List) (cont.)

• Linked List is a data structure which can change its size
during execution (dynamic allocation).
 Successive elements are connected by pointers (references).
 It can grow or shrink in size during execution of a program.
 It can be made just as long as required.
 It does not waste memory space.

header

A B C 
Linked List (Singly Linked List) 4

Linked List (Singly Linked List)

header

A B C D

• Linked List: is a series of connected nodes.

• Each node contains: node
 At least a piece of data (any type).
A
 Pointer to the next node in the list.
data pointer

• Header: pointer to the first node.

• The last node points to NULL.
 Linked List verse Array

• Like arrays, Linked List is a linear data structure.

• Unlike arrays, linked list elements are not stored at contiguous

location; the elements are linked using pointers.

 Linked List verse Array
Arrays can be used to store linear data of similar types, but arrays
have following limitations.
1) The size of the arrays is fixed: So we must know the upper limit
on the number of elements in advance. Also, generally, the allocated
memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive,
because room has to be created for the new elements and to create
room existing elements have to shifted.
 Linked List verse Array

A major difference between an Array and a Linked List is that:

whereas the elements in an Array are referenced by position (the

index), the elements of a Linked List are referenced by their

relationship to the other elements of the Linked List.

Linked List and Array 6

Linked List verse Array

• Advantages over arrays
• 1) Dynamic size
• 2) Ease of insertion/deletion
• Drawbacks:
• 1) Random access is not allowed. We have to access elements
sequentially starting from the first node. So we cannot do binary
search with linked lists.
• 2) Extra memory space for a pointer is required with each element
of the list.
• 3) Not cache friendly. Since array elements are contiguous
locations, there is locality of reference which is not there in case of
linked lists.
Linked List Terms 7

Linked List Terms

• Linked List: a collection of objects called nodes, where each node is
linked to its successor node in the list using a reference (pointer).

• Node: consists of two fields: data and pointer to the next node.

• Header: a node to denote the beginning of a Linked List.

• Nothing: null object (node) to denote the end of the Linked List.

• Predecessor: the item immediately before something.

• Successor: the item immediately after something.

header

Milk Bread Eggs Meat

Singly Linked List Design 8

Linked List Design

• We need to create a class called Node:

 We will create a Node class and instantiate a Node object each time
we add a new node to the list.

• We need another class called LinkedList for the list to handle

the references.

• The nodes in the list are connected via references to other nodes.
Singly Linked List Design – Node 9
Class

Node
public class Class
Node {
public int data;
public Node next;

public Node() {
data = 0;
next = null;
}
public Node(int d) {
data = d;
next = null;
}
}
Singly Linked List Design – LinkedList 10
Class

LinkedList
Class
• The LinkedList class is used to create the linkage for the
nodes.

• The class includes several methods for:

 adding nodes to the list,
 removing nodes from the list,
 traversing the list,
 finding a node in the list.
• We also need a constructor method that instantiates a list.

• The only data member in the class is the header node.

Singly Linked List Design – LinkedList 11
Class

Simple Linked List

Example
class LinkedList {
public Node head; // head of list
public static void Main(String[] args){
/* Start with the empty list. */
LinkedList llist = new LinkedList();
llist.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
// Linking nodes
head.next = second; // Link first node with the
second node
second.next = third; // Link first node with the
second node
}
}
Simple Linked List
Example
Singly Linked List – Printing a Linked List 21

Printing a Linked List

• PrintList method traverses the linked list and displays the
Element data of each node in the list.
private void PrintList() {
Node n = head;
if (n!= null){
while (n != null){
Console.WriteLine(n.data);
n = n.next;
}
else
Console.Write(“List isEmpty”);
}
Singly Linked List – Adding a New Node 12

Adding a New Node

• A node can be added in three ways

1. At the front of the linked list (add)

2. After a given node.(insert)

3. At the end of the linked list. (append)

Adding a new node at the front of
the linked list
public void push(int new_data){
/* 1 & 2: Allocate the Node & Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
 Add a node after a given node
• We are given pointer to a node, and the new node is inserted after
the given node.

newNode.next=B.next B.next=E
Pre_node.next=E E.next=B.next

A||next:B B||next:C C||next:D D||next:null

newNode||
next:null
 Add a node after a given node
public void insertAfter(Node prev_node, int new_data) {
/* 1. Check if the given Node is null */
if (prev_node == null){
Console.WriteLine("The given previous node cannot be null");
return;
}
/* 2. Allocate the Node & 3. Put in the data*/
Node new_node = new Node(new_data);

/* 4. Make next of new Node as next of prev_node */

new_node.next = prev_node.next;

/* 5. make next of prev_node as new_node */

prev_node.next = new_node;
}
Add a node at the end

last

While(last.next != null)
Last = last.next;

1. Searching to find the last node in the list

2. Node new_node=new Node(‘E’);
3. last.next=new_node;
 Add a node at the end
public void append(int new_data){
/* 1. Allocate the Node & 2. Put in the data3. Set next as null */
Node new_node = new Node(new_data);
/* 4. If the Linked List is empty, then make the new node as head */
if (head == null){
head = new_node;
return;
}
/* 4. This new node is going to be the last node, so make next of it as null */
new_node.next = null;
/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
return;
}
Singly Linked List – Removing a Node 17

• Removing a Node
Let us formulate the problem statement to understand the
deletion process. Given a ‘key’, delete the first occurrence of
this key in linked list.
• To delete a node from linked list, we need to do following
steps.
1) Find previous node of the node to be deleted.
2) Changed next of previous node.
3) Free memory for the node to be deleted.
temp Head
Prev

X
null
X

Prev.next = d;
Tmp.next=null;
Singly Linked List – Removing a Node 18

Removing a Node (cont.)

/* Given a key, deletes the first occurrence of key in linked list */
void deleteNode(int key) {
// Store head node
Node temp = head, prev = null;
// If head node itself holds the key to be deleted
if (temp != null && temp.data == key) {
head = temp.next; // Changed head
temp.next= null;
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change temp.next
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
// If key was not present in linked list
if (temp == null) { Console.WriteLine(“Not found”); return;}
// Unlink the node from linked list
prev.next = temp.next;
temp.next=null; free memory from the deleted node }
Limitations of Singly Linked List 22

Limitations of Singly Linked List

 One major advantage of Linked Lists over Arrays is that we can remove
an individual node, and the garbage collector will eventually pick it up.
 A downside of Linked Lists is that we don't have indexed access to the
nodes. If we want a node in the middle of the list, we have to start from
the beginning of the list.
 Singly Linked Lists have two other problems:
 The first is that: we can not go backwards. The reference in each node names
only the next item in the list.
 The second problem is that: if we need to remove, say, node b, our index
must reference node a, and then we must refer
index.getNext().getNext() in order to connect to node a's
reference to node c (dereferencing node b and effectively removing
“next“
it from
the Linked List).

 Is there another way? There is, but it requires a list with one extra
reference in each node, a Doubly Linked List.
Doubly Linked List 23

Doubly Linked List

 Each node points to the next node and to the previous node as well.
 There are two NULL: at the first and last nodes in the list.
 Advantages:
 Given a node, it is easy to visit its predecessor (previous).
 Convenient to traverse lists backwards.
Doubly Linked List 24

Doubly Linked List (cont.)

• In a Doubly Linked List, each node contains:
 Data (any type).
 Pointer to the next node (Forward Link)
:
next

 Pointer to the previous node (Backward Link) : prev

Doubly Linked List Node
next
A
prev data
Doubly Linked List Design – Node 25
Class

Node Class in a Doubly Linked

List class Node {
public
public int data;
public Node next; // Forward Link
public Node prev; // Backward Link

public Node() {
data = 0;
next = null;
prev = null;
}
public Node(int d) {
data = d;
next = null;
prev = null;
}
}
Singly Linked List Design – LinkedList 10
Class

Doubly LinkedList Class

• The doubly LinkedList class is used to create the linkage for
the nodes.

• The class includes several methods for:

 adding nodes to the list,
 removing nodes from the list,
 traversing the list,
 finding a node in the list.
• We also need a constructor method that instantiates a list.

• The only data member in the class is the header node.

Singly Linked List – Printing a Linked List 21

Printing a doubly Linked List

• PrintList method traverses the doubly linked list and
displays the Element data of each node in the list in forward
direction.

public void PrintListForward() {

Console.Write(“Printing in forward direction \n”);
Node n = head;
while (n != null){
Console.WriteLine(n.data);
n = n.next;
}
}
Singly Linked List – Printing a Linked List 21

Printing a doubly Linked List

• PrintList method traverses the doubly linked list and
displays the Element data of each node in the list in
Backward direction.

public void PrintListBackward() {

Console.WriteLine(“Printing in Backward direction \n”);
Node last = head;
//finding the last node first
while (last.next != null){
last= last.next ;
}
while (last != null){
Console.WriteLine(last.data);
last = last.prev;
} }
Singly Linked List – Adding a New Node 12

Adding a New Node to a doubly Linked List

• A node can be added in three ways

1. At the front of the doubly linked list

2. After a given node.

3. At the end of the doubly linked list.

Adding a new node at the front of the doubly linked list
public void push(int new_data){
/* 1 & 2: Allocate the Node & Put in the data*/
Node new_node = new Node(new_data);
if (head == null)
head = new_node;
else
{
new_node.next = head;
head.prev = new_node;
head = new_node;
}
}
 Add a node after a given node
• We are given pointer to a node, and the new node is inserted after
the given node.
 Add a node after a given node
public void insertAfter(Node prev_node, int new_data) {
if (prev_node == null){
Console.WriteLine("The given previous node cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
new_node.prev = prev_node;
prev_node. next = new_node;

if(new_node.next !=null)
new_node.next.prev = new_node;
}
Add a node at the end
 Add a node at the end
public void append(int new_data){
Node new_node = new Node(new_data);
Node last = head;
if (head == null){
head = new_node;
return;
}
while (last.next != null)
last = last.next;

last.next = new_node;
new_node.prev = last;
return;
}
Doubly Linked List – Removing a Node 17

Removing a Node
• Let us formulate the problem statement to understand the
deletion process. Given a ‘key’, delete the first occurrence of
this key in linked list.
• To delete a node from linked list, we need to do following
steps.
1) Find previous node of the node to be deleted.
2) Change next pointer of the previous node.
3) Change prev pointer of the next node of previous node.
4) Free memory for the node to be deleted.
Singly Linked List – Removing a Node 18

Removing a Node (cont.)

void deleteNode(Node del_node) {
/* base case */
if (head == null || del_node == null) {
return;
}
/* If node to be deleted is head node */
if (head == del_node) {
head = del_node.next;
head.prev=null
}
/* Change next only if node to be deleted is NOT the last node */
if (del_node.next != null) {
del_node.next.prev = del_node.prev;
}
/* Change prev only if node to be deleted is NOT the first node */
if (del_node.prev != null) {
del_node.prev.next = del_node.next;
}
/* Finally, free the memory occupied by del*/
del_node.next = null; del_node.prev= null;
return; }
The Circularly Liked List 32

The Circularly Liked List

• Is a list where the last node points back to the first node
(the
header node).
• The Figure below illustrates how a Circularly Linked List works.
• The only real change we have to make to our code is: to let
the
header node points to itself when we instantiate a new Linked List.
• If we do this, every time we add a new node the last node will point
to the header, since that link is propagated from node to node.

Milk Bread Eggs Meat

header
The Circularly Liked List 33

The Circularly Liked List (cont.)

LinkedList
public classClass
LinkedList
{ protected Node
header;

public LinkedList() {
count = 0;
header = New Node("Milk");
header.next = header;
}
.
.
.
}