$30
DS Lab 1 Linked List Solved
Lab 1
Linked List
After completed this tutorial, you can implement a list ADT with linked list. Please review Generic before starting this tutorial.
1. UML model of Linked list
The following figure presents an UML model of linked list:
• ListInterface represents public functions of linked list, e.g., add new item, remove an item.
• Node class represents an item (node) in linked list.
• MyLinkedList class implements ListInterface and includes items have Node types.
In the next section, we will approach how to implement a linked list based on the above UML model.
dcquang@it.tdt.edu.vn 1
2. Node class
Node is the basic item in list, thus we need to implement it first.
public class Node <E { private E data; private Node <E next; public Node(){ data = null; next = null;
}
public Node(E data){ this(data, null);
}
public Node(E data, Node <E next){ this.data = data; this.next = next;
}
public Node <E getNext(){ return next;
}
public E getData(){ return data;
}
public void setNext(Node <E n){ next = n;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
3. ListInterface interface
ListInterface defines the operations (methods) we would like to have in a List ADT.
import java.util.NoSuchElementException; public interface ListInterface <E { public void addFirst(E item); public void addAfter(Node <E curr, E item); public void addLast(E item);
public E removeFirst() throws NoSuchElementException; public E removeAfter(Node <E curr) throws
NoSuchElementException; public E removeLast() throws NoSuchElementException;
public void print(); public boolean isEmpty(); public E getFirst() throws NoSuchElementException; public Node <E getHead(); public int size();
public boolean contains(E item);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
4. MyLinkedList class
This MyLinkedList class will implement the ListInterface interface.
import java.util.NoSuchElementException;
public class MyLinkedList <E implements ListInterface<E { private Node <E head; private int numNode; public MyLinkedList(){ head = null; numNode = 0;
}
@Override
public void addFirst(E item){ head = new Node<E(item, head);
numNode++;
}
@Override
public void addAfter(Node<E curr, E item){ if(curr == null){ addFirst(item);
} else{
Node<E newNode = new Node<E(item, curr.getNext()); curr.setNext(newNode);
}
numNode++;
}
@Override
public void addLast(E item){ if(head == null){ addFirst(item);
}
else{
Node<E tmp = head; while(tmp.getNext() != null){ tmp = tmp.getNext();
}
Node<E newNode = new Node<(item, null);
tmp.setNext(newNode); numNode++;
}
}
@Override
public E removeFirst() throws NoSuchElementException{ if(head == null){ throw new NoSuchElementException("Can't remove element
from an empty list");
}
else{
Node<E tmp = head; head = head.getNext(); numNode--;
return tmp.getData();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
@Override public E removeAfter(Node<E curr) throws
NoSuchElementException{ if(curr == null){ throw new NoSuchElementException("Can't remove element
from an empty list");
} else
{
Node<E delNode = curr.getNext(); if(delNode != null) { curr.setNext(delNode.getNext()); numNode--;
return delNode.getData();
} else{ throw new NoSuchElementException("No next node to remove");
}
}
}
@Override public E removeLast() throws NoSuchElementException
{
if(head == null){ throw new NoSuchElementException("Can't remove element
from an empty list");
}
else{
Node<E preNode = null;
Node<E delNode = head; while(delNode.getNext() != null){ preNode = delNode;
delNode = delNode.getNext();
} preNode.setNext(delNode.getNext()); delNode.setNext(null); numNode--;
return delNode.getData(); }
}
@Override public void print(){ if(head != null){
Node<E tmp = head;
System.out.print("List: " + tmp.getData()); tmp = tmp.getNext();
while(tmp != null)
{
System.out.print(" - " + tmp.getData()); tmp = tmp.getNext();
}
System.out.println();
} else{
System.out.println("List is empty!");
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
}
}
}
@Override
public boolean isEmpty(){ if(numNode == 0) return true;
return false;
}
@Override
public E getFirst() throws NoSuchElementException{ if(head == null){ throw new NoSuchElementException("Can't get element
from an empty list");
} else{ return head.getData(); }
}
@Override
public Node<E getHead(){ return head;
}
@Override public int size(){ return numNode;
}
@Override
public boolean contains(E item){ Node<E tmp = head; while(tmp != null){ if(tmp.getData().equals(item)) return true;
tmp = tmp.getNext();
}
return false;
}
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
5. Test Integer Linked List
public class Test { public static void main(String[] args)
{
MyLinkedList<Integer list = new MyLinkedList<Integer(); list.addFirst(new Integer(2)); list.addLast(new Integer(3)); list.print();
}
}
1
2
3
4
5
6
7
8
9
6. Excercise
Exercise 1
Giving Fraction class as the following class diagram:
You need to implement a linked list to contain Fraction items.
Exercise 2
Suppose that we have an abstract method with signature as follow:
public E removeCurr(Node<E curr)
This method removes the node at position curr. You need to add this abstract method to your program and implement it.
Exercise 3
Suppose we are having a list of integer numbers, do the following requirements:
(a) Count the number of even item in the list.
(b) Count the number of prime item in the list.
(c) Add item X before the first even element in the list.
(d) Find the maximum number in the list.
(e) (*) Reverse the list without using temporary list.
(f) (*) Sort the list in ascending order.
