HNDIT3032

Data Structures
and Algorithms

Week 5-Linked List

 Generics in Java(Con)
• Java included support for writing generic class in J2SE
5.0 or JDK1.5 version
• The Generics framework allow us to define a class in
term of a set of parameters that can be use as the type
of declared variables , parameters , and return types
• Before Java SE 5 , Generics programming was heavily
dependent upon the java Object class that the root of
the hierarchy in a java programming language.
• Example :public class MyClass<T> {} This is a generic
class that can be instantiated with any class type such
as Integer , String , Double etc.
 Generics in Java
• You will have learned in the above lessons that
we can use the collection framework to build
a simple data structure concept in Java
without algorithm implementation (add(),
remove()).
• Likewise, we can do many implementations
very easily using Java generics.
 Generics in Java(Con)
• If you want to set the bubble sort algorithm, then you
have to arrange two items next to each other in an
array. But you have a problem if the data included in
that array is of string type. You have to implement a
separate method for that. example When your array is
stored in the form of mango, apple, banana, you will
have a problem when you want to sort mango and
banana because it is not an integer. So you have to
write a separate method for that. So by using Generics
in Java facility you will be able to create a generic
method regardless of data type.
•
Generics in Java(Con)
// use < T> to specify Parameter type T is Specific type
• class Gn<T> {
• // object of type T is declared
• T object;
• Gn(T obj) { [Link] = obj; } // constructor
• public T getObject() { return [Link]; }
• }
•

• //Driver class
• class Generics1 {
• public static void main(String[] args)
• {
• // instance of Integer type
• Gn<Integer> iObj = new Gn<Integer>(15);
• [Link]([Link]());
•

• // instance of String type

• Gn<String> sObj
• = new Gn<String>("GeeksForGeeks");
• [Link]([Link]());
• }}
Generics in Java(Con)
Generics in Java(Con)
Generics in Java(Con)
• public class Pairs <K,V>{ // Key (K) and Value (V)
• int x,y;
• private K key;
• private V val;
•

• public K getKey() { return [Link]; }

• public V getVal() { return [Link]; }
•

• public static Pairs dis()

• {
• Pairs p=new Pairs();
• [Link]="Amma";
• [Link]=90;
• p.x=900;
• p.y=800;
• return p;
• }
• public static void main(String a[])
• {
• Pairs pi;
• pi=[Link]();
• [Link]([Link]+" "+[Link]+""+pi.x);
• }
• }
 Return More Types in Method
• class Test<T> {
• // An object of type T is declared
• T obj;
• Test(T obj) {
• [Link] = obj;
• } // constructor
• public T getObject() { return [Link]; }
• }

• class TestRun {
• public static void main(String[] args)
• {
• // instance of Integer type
• Test<Integer> iObj = new Test<Integer>(15);
• [Link]([Link]());
• // instance of String type
• Test<String> sObj
• = new Test<String>("GeeksForGeeks");
• [Link]([Link]());
• //iObj = sObj; // This results an error
• }
• }
•
 Advantages of Generics
• Programs that use Generics has got many benefits
over non-generic code.
• 1. Code Reuse: User can write a
method/class/interface once and use it for any type
user want
• 2. Type Safety: Generics make errors to appear
compile time than at run time (It’s always better to
know problems in your code at compile time rather
than making your code fail at run time). Suppose you
want to create an ArrayList that store name of
students, and if by mistake the programmer adds an
integer object instead of a string, the compiler allows
it. But, when we retrieve this data from ArrayList, it
causes problems at runtime.
 Linked List
• Linked List:
To overcome the disadvantage of fixed size
arrays, linked list were introduced.
A linked list consists of nodes of data which are
connected with each other. Every node consist
of two parts data and the link to other nodes.
The nodes are created dynamically.
• Flexible space use Linked Lists
– Dynamically allocate space for each element as
needed
– Include a pointer to the next item
Linked list
– Each node of the list contains
• the data item (an object pointer in our ADT)
• a pointer to the next node

Data Next

object
 Linked Lists
• Collection structure has a pointer to the list head
– Initially NULL

Collection
Head
• Add first item Linked Lists
– Allocate space for node
– Set its data pointer to object
– Set Next to NULL
– Set Head to point to new node

Collection
node
Head
Data Next

object
• Add second item Linked Lists
– Allocate space for node
– Set its data pointer to object
– Set Next to current Head
– Set Head to point to new node

Collection
Head

node
node
Data Next Data Next

object2 object
The composition of a Linked List
• A linked list is called "linked" because each
node in the series has a pointer that points
to the next node in the list.

21
 Declarations
• First you must declare a data structure that
will be used for the nodes. For example, the
following code could be used to create a
list where each node holds a any data
types

22
• public class Node<T> {
• //data to store
• private T data;
• //referance to the next
• private Node<T> next;
• //constructor set the object
• Node()
• {
• data=null;
• next =null;
• }
• //data store with in node object
• Node(T data)
• {
• [Link]=data;
• [Link] =null;
• }
• public T getData() {
• return data;
• }
• public void setData(T data) {
• [Link] = data;
• }
• public Node<T> getNext() {
• return next;
• }
• public void setNext(Node<T> next) {
• [Link] = next;
• }
• }
 Declarations
• The next step is to declare a pointer to
serve as the list head, as shown below.
public class List<T> {
//head of the List class
private Node<T> head;
//count variable
private int count;
//create an empty list
public List()
{
[Link]=null;
[Link]=0;
}
}

24
• Once you have declared a node data structure
and have created a NULL head pointer, you
have an empty linked list.
• The next step is to implement operations with
the list.
 Linked List Operations

• Appending a Node to the List

• Traversing the List
• Inserting a Node
• Deleting a Node
 Appending a Node to the List
• To append a node to a linked list means to add the node to
the end of the list.
• The pseudocode is shown below.
Create a new node.
Store data in the new node.
If there are no nodes in the list
Make the new node the first node.
Else
Traverse the List to Find the last node.
Add the new node to the end of the list.
End If.

27
• public void addEnd(T data)
• {
• //check list is empty
• if([Link]())
• {
• [Link](data);
• }else {
• //cretae new node
• Node<T> node=new Node<>(data);
• //add to the end of list
• Node<T> current=head;
• while([Link]()!=null)
• {
• current=[Link]();
• }
• //here we set the new node to next referance of last node
• [Link](node);
• [Link](null);
• count++;
• }
• }
 Stepping Through the Program
• First, the list is checked for empty and if it is empty,
the addFront(data) method has been called to add
data to the front.
• Otherwise, a new node is created because data
needs to be entered at the end of the list.
• The data to be entered into that node is also given.
• Then the while loop finds the last node because the
last node is Null.
• Therefore, the loop finds the node by doing the next node until
it is not null.
• By comparing the last found node with the next set
node, our node set as the last node in the list.
• Last Node set be as Null
29
 Traversing the List
• The displayList member function traverses the list,
displaying the value member of each node. The
following pseudocode represents the algorithm.

Assign List head to node pointer.

While node pointer is not NULL
Display the value member of the node pointed to by node pointer.
Assign node pointer to its own next member.
End While.

31
• public void printData()
• {
• if([Link]()) {
• [Link]("List is Empty:..");
• return;
• }
• [Link]("[");
• if(![Link]())
• {
• [Link]("%s",[Link]());
• }
• Node<T> current=[Link]();
• while(current!=null)
• {
• [Link](", %s",[Link]());
• current=[Link]();
• }
• [Link]("]");
• }
 Stepping Through the Program
• First check if the list is empty and if it is empty
then a massage will be given as empty.
• If it is not empty, the head value is printed
first.
• A new node will be created as current and
equal to the after node of the head .
• The unfortunate node of a linked list is null, so
the interaction is done by the while loop until
the null node is found.
 Inserting a Node
• Using the linked List structure again, the
pseudocode on the next slide shows an
algorithm for finding a new node’s proper
position in the list and inserting there.
• The algorithm assumes the nodes in the list
are already in order.

34
Create a new node.
Store data in the new node.
If there are no nodes in the list
Make the new node the first node.
Else
Find the first node whose value is greater than or equal
the new value, or the end of the list (whichever is first).
Insert the new node before the found node, or at the end of
the list if no node was found.
End If.

35
public void addFront(T data)
{
//create new node
Node<T> node=new Node<>(data);
if([Link]())
{
head=node;
}
else//if the list not empty
{
[Link](head);//set the head to the next pointer of new node
head=node;//make it first node
}
count++;
}
 Stepping Through the Program
• First a node is created and the data is given to it
• The Linked List is checked for empty, and if it is
empty, the created node is equal to the head.
• Since the new node must be entered first in the
Linked list, the head is equal to the next node
and the new node is equal to the head.

37
 Deleting a Node
• Deleting a node from a linked list requires two
steps:
– Remove the node from the list without breaking
the links created by the next pointers
– Deleting the node from memory
• The remove() function begins on the next
slide.
• public boolean remove(T data)
• {//case 1 check the list is empty
• if([Link]())
• {return false;
• }
• if([Link]().equals(data))
• {
• head=[Link]();
• count--;
• return true;}
• else {
• //node having the between the node or node is last node
• Node<T> current=head;
• Node<T> pre=null;
• while(current!=null )
• { if( [Link]().equals(data))
• { [Link]([Link]());//skip the current node
• count--;
return true;
• }//update navigate pointer
• pre=current;
• current=[Link]();
• }}
• return false;//node not found data}
 Stepping Through the Program
• Check linked list is empty ,if it is empty return false
• If it is not empty , The given data should be found in the
linked list. First, it is checked whether the data is the same
as the head. The head node is equal to the next node.
• Otherwise, while loop is used to check all other nodes until
null. If we find the node related to our data while checking,
it should be deleted.
• The node found is equal to the first empty node and it is
deleted. Then the empty node is equal as the (pre)current
node.
• Finally If there is no node according to the given data, it will
be returned as false.
 Exercise: ………..
• 1.) Update the program given to you and
display the data in reverse order in the linked
list.
• 2.) Write a short noted following topic
• 1.) Linked List vs Arraylist
• 2.) Linked List vs Array