COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 5-2 : Singly Linked Lists
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Singly Linked Lists
LINKED LISTS
IMPLEMENTATIONS
There are different implementations of a list:
Array list
Singly linked list Doubly linked list
Idea: the elements in the list are linked using pointers
Array list
Linked list
“nodes”
null
null
null
null
null
size = 4
Array list
Linked list
“nodes”
null
null
null
null
null
Array slots are in consecutive locations (addresses) in memory, but objects (elements) can be anywhere.
Linked list “nodes” and objects (elements) can be anywhere in memory.
SINGLY LINKED LIST NODE
class SNode { Shape element; SNode next;
}
myNode
next element
null
SNode myNode = new SNode(); n.element = new Shape( );
SINGLY LINKED LIST
We think of a linked list as a sequence of nodes, along with a reference to the first (head) and last (tail) node.
head
tail
null
SINGLY LINKED LIST
public class SLinkedList {
private SNode head;
private SNode tail;
private int size;
:
private class SNode {
Shape element;
SNode next; }
}
4
list
head
tail
size
null
SLinkedList list = new SLinkedList();
:
LINKED LIST OPERATIONS
addFirst ( e )
removeFirst( )
addLast ( e )
removeLast( )
……. many other list operations
LINKED LIST OPERATIONS – addFirst( )
BEFORE
AFTER
4
head
tail
size
head
tail
size
5
null
null
addFirst(e) – PSEUDOCODE
SNode newNode = new SNode(); newNode.element = e; newNode.next = head;
// edge case
if (head == null)
tail = newNode;
head = newNode;
size = size +1;
e
newNode
next element
54
head
tail etc size
LINKED LIST OPERATIONS – removeFirst( )
BEFORE
AFTER
4
5
head
tail
size
head
tail
size
null
null
removeFirst() – PSEUDOCODE
temp
head tail
size
temp
head tail
size
next element
5
SNode temp = head;
head = temp.next;
temp.next = null; // not required size = size – 1;
return temp.element;
BEFORE AFTER
etc
next element
null
etc
4
removeFirst() – EDGE CASES (SIZE IS 0 OR 1)
SNode temp = head;
if (size == 0)
throw exception
head = temp.next; temp.next = null; size = size – 1; if (size == 0)
tail = null;
return temp.element;
Size = 0 Size = 1
temp
head tail
size
Before After
null
null
null
0
temp next element temp
head head tail tail size size
next element
null
null
1
null
null
0
WORSE CASE TIME COMPLEXITY (N = LIST SIZE)
array list addFirst() O( N ) removeFirst() O( N )
For arraylist with N elements, recall that add(0, e) and remove(0) required a loop with N iterations
linked list O( 1 ) O( 1 )
For linked lists the implementation of addFirst() and removeFirst() does not depend on the number of elements in the list
WORSE CASE TIME COMPLEXITY (N = LIST SIZE)
addFirst() removeFirst() addLast() removeLast()
array list O( N ) O( N )
O( 1 )* O( 1 )
linked list O( 1 ) O( 1 )
? ?
*if array is not full
LINKED LIST OPERATIONS – addLast( )
BEFORE
AFTER
4
head
tail
size
head
tail
size
5
null
null
addLast(e) – PSEUDOCODE
: next element
4
head
// create a new node tail SNode newNode = new SNode(); size
e
newNode.element = e;
// add it at the end
tail.next = newNode; head
tail = tail.next;
size = size + 1;
tail
size
e
newNode
null
null
BEFORE AFTER
: next element
5
newNode
null
LINKED LIST OPERATIONS – removeLast( )
BEFORE
AFTER
4
5
head
tail
size
head
tail
size
null
null
Problem: we have no direct way to access the node before tail!
removeLast() – PSEUDOCODE SNode tmp = head;
while (tmp.next != tail) head
next element
5
tmp = tmp.next;
tail
size
temp
null
removeLast() – PSEUDOCODE SNode tmp = head;
while (tmp.next != tail) head
next element
4
tmp = tmp.next;
tail = tmp; tail.next = null;
size = size – 1;
// to return the element,
// you need to do a bit more work
tail
size
temp
null
null
// edge cases for size = 0 and 1 to be added
removeLast() – EDGE CASES (SIZE IS 0 OR 1) temp
if (size == 0)
throw exception
if (size == 1)
head = null;
tail = null; else {
… }
size = size – 1;
Size = 0 Size = 1
head tail
size
head tail
size
Before After
null
null
null
0
next element
next element
null
1
null
null
0
head tail
size
null
WORSE CASE TIME COMPLEXITY (N = LIST SIZE)
addFirst() removeFirst() addLast() removeLast()
array list O( N ) O( N )
O( 1 )* O( 1 )
linked list O( 1 ) O( 1 )
O(1) O(N)
*if array is not full
In the next videos: Doubly Linked Lists