Week 3 : List

STIA2024
Data Structures & Algorithm
Analysis

1
 Lecture Outlines

 Contiguous List
 Self-referential Classes
 Dynamic Memory Allocation
 Linked list
- Basic operations of linked list

2
 Learning Objectives
• To describe the concept of linked list and
contiguous list,
• To describe the advantages and
disadvantages between contiguous and
linked list,
• To apply the use of dynamic and static
memory allocation in programming, and
• To apply those operations of linked list in
programming.
3
 What is a Data Structure?

 A data structure is a collection of data organized

in some fashion.
 A data structure not only stores data, but also
supports the operations for manipulating data in
the structure.
 For example, an array is a data structure that
holds a collection of data in sequential order. You
can find the size of the array, store, retrieve, and
modify data in the array.
 Object-Oriented Data Structure
 In object-oriented thinking, a data structure is an object
that stores other objects, referred to as data or elements.
 So some people refer a data structure as a container
object or a collection object.
 To define a data structure is essentially to declare a
class. The class for a data structure should use data
fields to store data and provide methods to support
operations such as insertion and deletion.
 To create a data structure is therefore to create an
instance from the class. You can then apply the methods
on the instance to manipulate the data structure such as
inserting an element to the data structure or deleting an
element from the data structure.
 Linear Data Structures

 Three linear data structures to be introduced in

this course are:
1. Lists: is a collection of data stored sequentially. It
supports insertion and deletion anywhere in the list
2. Stacks: can be perceived as a special type of the list
where insertions and deletions take place only at the
one end, referred to as the top of a stack
3. Queues: represents a waiting list, where insertions
take place at the back (also referred to as the tail of)
of a queue and deletions take place from the front
(also referred to as the head of) of a queue
 Lists
 A list is a popular data structure to store data in sequential
order.
 For example, a list of students, a list of available rooms, a
list of cities, and a list of books, etc. can be stored using
lists.
 The common operations on a list are usually the following:
 Retrieve an element from this list.
 Insert a new element to this list.
 Delete an element from this list.
 Find how many elements are in this list.
 Find if an element is in this list.
 Find if this list is empty.
 Two Ways to Implement Lists
 One is to use an array to store the elements
(contiguous list).
 The other approach is to use a linked structure
(linked list). A linked structure consists of nodes.
Each node is dynamically created to hold an
element. All the nodes are linked together to form
a list.
 Contiguous List
 Use an array to store data
 Size of the list is specified by user. The size can’t
be altered.
 It is called “static/fixed size” data structure.
 It is good implementation when:
 The number of data are small
 The size of list is already known
 The operations of deletion and insertion are
happened rarely.
 When using random access
 Contiguous List

 Disadvantages/ problems:
 The size of list is fixed
 A lot of operation of deletion and
insertion - updating the record will
involve shifting.
 Waste memory when a space is not used
completely

10
Common Operations of Contiguous
List
1. Create a list
2. Find if the list is empty or full
3. Add a new element to the list
4. Remove an element from the list
5. Search an element on the list
 Contiguous List - Create a List
 Syntax :

typeOfList [ ] listName = new typeOfList[SIZE];

 E.g.: int myList[ ] = new int[10];

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
myList
Contiguous List – Find if the list is
Empty?
Algorithm : Implementation:

if number of elements is 0 public boolean isEmpty( ) {

if(num== 0)
– return true
return true;
else else
– return false return false;
}
Contiguous List – Find if the list is
Full?
Algorithm : Implementation:

if number of elements is public boolean isFull( ) {

if(num== myList.length)
equals to array size return true;
– return true else
else return false;
}
– return false
 Contiguous List - Adding Data

Making room to insert “Carla” as third entry in an array

Note: Must shift existing entries to provide space for a new data to be inserted
Except when adding as last entry
Contiguous List - Adding Data
If the list is empty
set new data as a first element
increase number of element (num)
Else if the list is full
display error message
else
find an index location of new data
set x=num
while x > search index
set an array element of [x-1] to be an array
element of [x]
decrease value of x
set new data at position of search index
increase value of num
 Contiguous List - Adding Data

public void add(int newData) {

if (isEmpty( )) {
myList[0]=newData;
num++;
}
else if (isFull( ))
System.out.println(“List is full");
else {
int index = findIndex(newData);
for (int x=num; x >index; x- -)
myList[x]=myList[x-1];
myList[index]=newData;
num++;
}
}
Contiguous List - Removing Data

Removing “Bob” by shifting array entries

Note: Must shift existing entries to avoid gap in the array
Except when removing last entry
Contiguous List - Removing Data
If the list is empty
Display error message
else
find an index of data to be removed
if found==-1
display error message “Data not found”
else
x = found
while x<num
set an array element of [x+1] to be an array element
of [x]
increase value of x
Decrease value of num
Contiguous List - Removing Data
public void remove (int target)
{
if (isEmpty( ))
System.out.println(“List is empty");
else{
int found = search(target);
if (found==-1)
System.out.println(“Data not found");

else{
for(int x=found; x<num;x++ )
myList[x]=myList[x+1];
num--;
}
}
}
Contiguous List - Searching Data

Set index=0
While index < number of elements (num)
if array element == target
return index
increase value of index
return -1 (if data not found)
Contiguous List - Searching Data

public int search(Object target)

{
for (int index=0; index <num; index++)
if (myList[index].getData( ).equals(target))
return index;
return -1;
}
Contiguous List - Find Index of
Data
public int findIndex(Object target)
{
for (int index=0; index <num; index++) {
if (myList[index].getData( ).compareTo(target)>0))
return index;
}
return num;
}
 Contiguous List - Display List
Elements
while index < number of elements (num)
display an array elements
increase value of index

public void Display( )

{
for (int index=0; index <num; index++)

System.out.println(myList[index].toString( ));

}
 Self- referential Classes
 An Object that will refer to the others object from the
same classes
 It is used when implementing the linked list’s data
structure
 Data/ information is stored in a node.
 Generally, every node has 2 data fields :
Info/ data - has related data
link/ pointer - pointing to the next node
 Pointer is a “self referential classes” which point to
the other node
Info link Info link
25
Nodes
 Dynamic Memory Allocation
 Linked List -
 Memory will be allocated when a space is required.
 Memory will be released when a space is not required
anymore.

 Contiguous List -
 Memory cannot be released
 Memory will be wasted when a space is not required

26
 Linked List
 A collection of list nodes where each node contains
info (data) and a link (reference) to the next node in the
linked list
 Consists of several nodes (unlimited nodes)
 To overcome the shifting problem.

Data link

One node

Two linked nodes with a) primitive data; (b) object data

27
 Linked List
 We can represent a list node as an object of type
Node with two data fields, info (type Object) and link
(type Node):
class Node
{
// Data fields for Node
private Object info; // data stored in the node
private Node link; // link to next node

< constructor>
….
<Accessor and Mutator methods: getInfo, setInfo, getLink, setLink >
……

} // end Node

28
 Linked List
 Every list must have a pointer called “head” or “first
node” or ”front”.
 If list is empty, head must be null.
 If list is not empty, head must be pointed to the first
node and last node must be pointed to null.

null OR List is empty

head head

2 4 6 List is not empty

head
29
 Linked List – Class Node
/* Node.java Authors: Koffman & Wolz
* Represents a node with information and link fields.
*/
class Node
{
// Data fields for Node
private Object info; // data stored in the node
private Node link; // link to next node
// Methods
// Constructors
// postcondition: Creates a new empty node.
public Node() {
info = null;
link = null;
}
// postcondition: Creates a new node storing obj.
public Node(Object obj) {
info = obj;
link = null;
}
// postcondition: Creates a new node storing obj
// and linked to node referenced by next.
public Node(Object obj, Node next) {
info = obj;
link = next;
}
30
 Linked List – Class Node

// accessors
public Object getInfo()
{
return info;
}
public Node getLink()
{
return link;
}

// mutators
public void setInfo(Object newInfo)
{
info = newInfo;
}
public void setLink(Node newLink)
{
link = newLink;
}
}

31
 Basic Operations of Linked List
1) Create a linked list
2) Inserting a node in linked list
a) First node
b) Last node
c) Between 2 nodes – based on searching required node
3) Removing a node from linked list
a) First node
b) Last node
c) Between 2 nodes – based on searching required node
4) Traversing the nodes in linked list

32
 Create a Linked List
 Pointer “head” must be initialized with null.

ListNode lst = new ListNode();

head

33
 Inserting a First Node
 Algo.
 Create a new node
 If list is empty
 Set pointer “head” to new node
 else
 Set pointer “link” of new node to the first node
 Set pointer “head” to the new node
 Increase the number of nodes.

head

2
newNode
34
Inserting a First Node – Empty List
Node newNode = new Node(new Integer(8))
if (head == null)
head = newNode;
else {
newNode.setLink(head); // newNode.link = head
head = newNode;
}
count++;

head = newNode

X 8
head
newNode

8 Insert 8
head 35
Inserting a First Node – Non-empty
List
Node newNode = new Node(new Integer(7))
if (head == null)
head = newNode;
else {
newNode.setLink(head); // newNode.link = head
head = newNode;
}
count++;

X 8
head
head = newNode newNode.link = head
7 X
Insert 7
newNode

7 8 36
head
 Inserting a Last Node
 This process needs to be traversed from one node to
another node until reaching the last node.
 We need a pointer called “current” to traverse nodes
 Algo.
 Create a new node
 If list is empty
 Set pointer “head” to the new node
 else
set pointer “current” to the first node
Loop until pointer link of “current” not equal to null.
set pointer “current” to the next node //current = current.link
set pointer link of “current” to a new node
 Increase the number of nodes.

37
 Inserting a Last Node
Node newNode = new Node(new Integer(9))
if (head == null)
head = newNode;
else
{
Node current = head;
// traversing nodes
while (current.getLink() != null) // current.link != null
current = current.getLink(); // current = current.link
current.setLink(newNode); // current.link= newNode
}
count++;

38
Inserting a Last Node – Empty List
Node newNode = new Node(new Integer(8))
if (head == null)
head = newNode;
else
{
……..
}
head = newNode

X 8
head
newNode

8 Insert 8
head

39
Inserting a Last Node – Non-empty
List
Node newNode = new Node(new Integer(10))
if (head == null)
head = newNode;
else
{
Node current = head;
while (current.getLink() != null) // current.link != null
current = current.getLink(); // current = current.link
current.setLink(newNode); // current.link= newNode
}

40
Inserting a Last Node – Non-empty
List
Insert 10

current.link= newNode
8 9 X 10
head
current = head
newNode
current = current.link

current

8 9 10
head

41
 Inserting Between Two Nodes
 There are several ways to insert a new node
in between two nodes of linked list
 Examples:
 By position of node
 By value via searching the required node

 In this case, we use second technique

 Inserting nodes after searching the required
data/info.
 A new node will be inserted after searching the
required node.

42
 Inserting Between Two Nodes
 Algo.
 Create a new node
 If list is empty
Set pointer “head” to new node
 else
Set pointer “current” to the first node
Loop until current != null
if data of current node is not equal to target
set the pointer “current” to the next node
else if data of current node is equal to target
set pointer “link” of new node to pointer” link” of current node.
set link of pointer “current” to new node
break
If current is equal to null
“The target is not exist”
End loop
 Increase the number of nodes.

43
 Inserting Between Two Nodes
Node newNode = new Node(new Integer(5))
if(head==null)
head = newNode;
else{
Node current= head;
while (current != null){
if(current.getInfo()!= target)//current.info!=target
current = current.getLink(); // current = current.link
else if(current.getInfo() == target){ //current.info == target
newNode.setLink(current.getLink()); //newNode.link=current.link
current.setLink(newNode); // current.link = newNode
break;
}
if(current==null)
System.out.println(“The target is not exists”);
}
}
count++;

44
 Inserting Between Two Nodes
Node newNode = new Node(new Integer(5))
if (head == null)
head = newNode;
else
{
Node current= head;
while (current != null){
if(current.getInfo()!= target)//current.info!=target
current = current.getLink(); // current = current.link
else if(current.getInfo() == target){ //current.info == target
newNode.setLink(current.getLink()); //newNode.link=current.link
current.setLink(newNode); // current.link = newNode
break; }
if(current==null)
System.out.println(“The target is not exists”);
}
}
count++;

45
 Inserting Between Two Nodes
current.link = newNode

2 4 X 7
head
current= head
5 X
current newNode newNode.link = current.link
current = current.getLink();

Insert 5

2 4 5 7
head

46
 Removing First Node
 Algo.
 If list is empty
 Display an error message
 Else
 If only one node
 Set pointer “head” to null
 Else
 Set pointer “head” to the next node
 decrease the number of nodes.

2
head head

47
 Removing First Node
head = head.getLink() // head = head.link

X 2 4 5 7
head

4 5 7
head

remove 2

48
 Removing a Last Node
 Before removing node, it must be checked whether the
list is empty or not.
 This process needs to be traversed from one node to
another node until reaching last node.So, it needs
more times to reach last node.
 Algo.
 Set pointer “current” to the first node
 Loop until current.link.link is not equal to null
 Set pointer “current” to the next node
 Set pointer “link” of current node to null.
 Decrease the number of nodes.
49
 Removing a Last Node
Node current = head;

// current.link.link != null
while (current.getLink().getLink() != null)
current = current.getLink();
current.setLink(null); // current.link = null
count--;

current.link().link() != null

2 4 5 X 7
head
current.link = null
current = current.getLink();

current remove 7

2 4 5
50
head
 Removing Between Two Nodes
 There are several ways to remove nodes in between
two nodes of linked list
 Examples:
 By position of node
 By value via searching the required node
 In this case, we use second technique
 Must search the target first to delete that data
 A certain node will be removed based on searching
required node.

51
 Removing Between Two Nodes
 Algo.
 If list is empty
Msg “cannot be removed”
 Else
if data/ info of first node is equal to target
set pointer “head” to second node
else
set pointer “before” to null
set pointer current to the first node
Loop until data/ info of current node is not equal to target AND
pointer “link” of current is not equal to null
set pointer before to pointer “current”
set pointer “current” to the next node
if data/info of current node is equal to target
set pointer link of “before” to pointer”link” of current
else
52
msg “target is not exists”
 Removing Between Two Nodes
if (head == null)
System.out.println(“Cannot delete data”;
else if (head.getInfo() == target)
head = head.getLink();
else
{
Node before = null;
Node current= head;

// current.info != target
while ( (current.getInfo() != target) && (current != null) )
{
before = current;
current = current.getLink(); // current = current.link
}
if (current.getInfo() == target) // current.info == target
before.setLink(current.getLink()); // before.link = current.link

else
System.out.println(“The target is not exists”); 53
}
 Inserting Between Two Nodes
if (head == null)
System.out.println(“Cannot delete data”);
else if (head.getInfo() == target)
head = head.getLink();
else
……..

head = head.getLink();

X 2 4 5 7
head

remove 2
4 5 7
head
54
 Removing Between Two Nodes
if (head == null)
….
else if (head.getInfo() == target)
…..
else
{
Node before = null;
Node current= head;

// current.info != target
while((current.getInfo() != target) && (current != null) )
{
before=current;
current = current.getLink(); // current = current.link
}
if (current.getInfo() == target) // current.info == target
before.setLink(current.getLink());// before.link = current.link

else
System.out.println(“The target is not exists”); 55
}
 Removing Between Two Nodes

X before.link = current.link
before
before = current

2 4 X 5 7
head

current = current.getLink();
current

2 4 7
head

remove 5

56
 Traversing Nodes
 Traversing is useful when
 Displaying information for every node in the list
 Searching an information in the list
 To get number of nodes and etc……
 Algo
 Set pointer “current” to the first node
 Loop until pointer “current” Is not equal to null
 Set pointer “current “ to the next node

57
 Traversing Nodes
System.out.print(“Data = “);
Node current = head;
While (current!= null)
{
System.out.println(current.getInfo());
current = current.getLink(); // current = current.link
}

2 4 5 7
head

current = current.getLink();
current

Data = 2 4 5 7 Display all data in the lists

58
 List in Java
List is one of the interfaces specified in the Java
Collection Framework
The JCF provides several types of collections,
such as sets, lists, queues and maps in the
form of interfaces.
A collection is a container object that represents a
group of objects, often referred to as elements
 Java Collection Framework
hierarchy (partial).
Set and List are subinterfaces of Collection.

SortedSet TreeSet

Set AbstractSet HashSet LinkedHashSet

Collection AbstractCollection
Vector Stack

List AbstractList
ArrayList

AbstractSequentialList LinkedList

Interfaces Abstract Classes Concrete Classes

The Collection Interface
The Collection interface is the root interface
Collection for manipulating a collection of objects.
+add(o: Object): boolean Adds a new element o to this collection
+addAll(c: Collection): boolean Adds all elements in the collection c to this collection
+clear(): void Removes all the elements from this collection
+contains(o: Object): boolean Returns true if this collection contains the element o
+containsAll(c: Collection):boolean Returns true if this collection contains all the elements in c
+equals(o: Object): boolean Returns true if this collection is equal to another collection o
+hashcode(): int Returns the hash code for this collection
+isEmpty(): boolean Returns true if this collection contains no elements
+iterator(): Iterator Returns an iterator for the elements in this collection
+remove(o: Object): boolean Removes the element o from this collection
+removeAll(c: Collection): boolean Removes all the elements in c from this collection
+retainAll(c: Collection): boolean Retains the elements that are both in c and in this collection
+size(): int Returns the number of elements in this collection
+toArray(): Object[] Returns an array of Object for the elements in this collection
+toArray(array: Object[]): Object[] Returns an array for the elements with the specified type

Iterator
+hasNext(): boolean Returns true if this iterator has more elements to traverse
+next(): Object Returns the next element from this iterator
+remove(): void Removes the last element obtained using the next method
Removes all the elements from this collection
 Iterator for List traversal
Iterator enables us to iterate over or traverse a
collection
Iterator is an interface (in java.util)
It contains only three methods:
hasNext()
next()
remove()
Most collections have an iterator() method that will
return an implementation of these methods
 Iterator for List traversal

Iterator Approach:

Iterator it = list.iterator();
while (it.hasNext())
System.out.println(it.next());
 List Traversal

Using a JDK 1.5, you can use enhanced “for each”

loop without using an iterator, as follows:

for (Object element : list)

System.out.print(element + " ");
 The List Interface
Collection

List
+add(index: int, element: Object) : boolean Adds a new element at the specified index
+addAll(index: int, collection: Collection) : Adds all elements in the collection to this list at the
boolean specified index
+get(index: int) : Object Returns the element in this list at the specified index
+indexOf(element: Object) : int Returns the index of the first matching element
+lastIndexOf(element: Object) : int Returns the index of the last matching element
+listIterator() : ListIterator Returns the list iterator for the elements in this list
+listIterator(startIndex: int) : ListIterator Returns the iterator for the elements from startIndex
+remove(index: int) : int Removes the element at the specified index
+set(index: int, element: Object) : Object Sets the element at the specified index
+subList(fromIndex: int, toIndex: int) : List Returns a sublist from fromIndex to toIndex
 List Iterator
 A ListIterator has the usual Iterator methods:
hasNext(), next(), and remove(),
 but it also has methods such as:
-hasPrevious()
-previous()
-add(obj)
 that make it possible to move backwards in the
list and to add an item at the current position of
the iterator.
 The List Iterator
Iterator

ListIterator
+add(o: Object) : void Adds the specified object to the list
+hasPrevious() : boolean Returns true if this list iterator has more elements
when traversing backward.
+nextIndex() : int Returns the index of the next element
+previousIndex() : int Returns the index of the previosu element
+previous() : Object Returns the previous element in this list iterator
+set(o: Object) : void Replaces the last element returned by the previous
or next method with the specified element
 Java List classes
 Several concrete classes implement the List
interface such as:
ArrayList
Vector
LinkedList
 They are categorised based on the type of data
structures used to implement the lists:
- Array (ArrayList & Vector)
- Sequence of linked data or linked list
(LinkedList)
 Using ArrayList Class

This example creates an array list with specified

capacity, and inserts elements into the specified
location & remove an element in the list.

Finally, the example traverses the list forward

using the iterator.
Using ArrayList Class
List aList = new ArrayList(5);
aList.add(1);
aList.add(2);
Initial capacity (optional)
aList.add(3);
aList.add(1);
aList.add(0,10);
aList.add(3,30);
aList.remove(1);
Iterator listItr = aList.iterator();
while (listItr.hasNext()) {
System.out.print(listItr.next() + " ");
}
OUTPUT: 10 2 30 3 1
 The Vector Class
In Java 2, Vector is the same as ArrayList, except
that Vector contains the synchronized methods for
accessing and modifying the vector. None of the
new collection data structures introduced so far
are synchronized.

If you don’t need synchronization, use ArrayList

since it work faster than Vector
 The Vector Class, cont.
List

Vector
+addElement(o: Object): void Appends the element to the end of this vector
+capacity(): int Returns the current capacity of this vector
+copyInto(anArray: Object[]): void Copies the elements in this vector to the array
+elementAt(index: int): Object Returns the object at the specified index
+elements(): Enumeration Returns an emulation of this vector
+ensureCapacity(): void Increases the capacity of this vector
+firstElement(): Object Returns the first element in this vector
+insertElementAt(o: Object, index: int): void Inserts o to this vector at the specified index
+lastElement(): Object Returns the last element in this vector
+removeAllElements() : void Removes all the elements in this vector
+removeElement(o: Object) : boolean Removes the first matching element in this vector
+removeElementAt(index: int) : void Removes the element at the specified index
+setElementAt(o: Object, index: int) : void Sets a new element at the specified index
+setSize(newSize: int) : void Sets a new size in this vector
+trimToSize() : void Trims the capacity of this vector to its size
 Using the Vector Class

Vector v=new Vector();

System.out.println("Before adding elements:"); OUTPUT:
System.out.println("Capacity=" + v.capacity()) ; Before adding elements:
System.out.println("size="+ v.size()); Capacity=10
v.addElement(1); size=0
v.addElement(2); After adding elements:
v.addElement(3); 1
v.add(1, 4);
4
System.out.println("After adding elements:");
Iterator listItr = v.iterator();
2
while (listItr.hasNext()) { 3
System.out.println(listItr.next() + " "); capacity=10
} Size = 4
System.out.println("capacity=" + v.capacity());
System.out.println("Size = "+v.size());
 LinkedList Class

List AbstractSequentialList

LinkedList
+addFirst(o: Object) : void Adds the object to the head of this list
+addLast(o: Object) : void Adds the object to the tail of this list
+getFirst() : Object Returns the first element from this list
+getLast() : Object Returns the last element from this list
+removeFirst() : Object Returns and removes the first element from this list
+removeLast() : Object Returns and removes the last element from this list
 Using LinkedList Class

This example creates a linkedlist, and inserts &

removes elements from the list.

Finally, the example traverses the list forward &

backward using the ListIterator.
 Using LinkedList Class
List lList = new LinkedList();
lList.add("red");
lList.add(0,"green");
lList.add("blue");
lList.add(1,"yellow");
lList.remove(3);
ListIterator listItr = lList.listIterator();
while (listItr.hasNext()) {
System.out.println(listItr.next() + " ");
}
System.out.println();
listItr = lList.listIterator(lList.size());

while (listItr.hasPrevious()) {
System.out.println(listItr.previous() + " ");
}
Using LinkedList Class
Output:

green
yellow
red

red
yellow
green
 References
 Data Structures and Abstractions with Java . Authors: Frank M.
Carrano & Walter Savitch . Chapter 5 and 6

 Problem Solving with Java. Authors: Elliot B. Koffman & Ursula

Wolz. Chapter 10.

 Data Structures & Other Objects Using Java. Author: Michael Main
Chapter 4

78
 Conclusion

Q & A Session

79
 Exercise
 If myList is an empty list, what is the output produced
after the following statements execute?
LinkedList myList = new LinkedList();
myList.add("alpha");
myList.add(0,"beta");
myList.add("gama");
myList.add(2,"delta");
myList.add("alpha");
myList.remove(1);
myList.remove("delta");
myList.remove(2);
for (Object element : myList)
System.out.print(element + " "); 80