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.

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) throwsNoSuchElementException; 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;}@Overridepublic void addFirst(E item){ head = new Node<E>(item, head);numNode++;}@Overridepublic 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++;}@Overridepublic 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++;}}@Overridepublic E removeFirst() throws NoSuchElementException{ if(head == null){ throw new NoSuchElementException(Cant remove elementfrom 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) throwsNoSuchElementException{ if(curr == null){ throw new NoSuchElementException(Cant remove elementfrom 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(Cant remove elementfrom 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

}

}}@Overridepublic boolean isEmpty(){ if(numNode == 0) return true;return false;}@Overridepublic E getFirst() throws NoSuchElementException{ if(head == null){ throw new NoSuchElementException(Cant get elementfrom an empty list);} else{ return head.getData(); }}@Overridepublic Node<E> getHead(){ return head;}@Override public int size(){ return numNode;}@Overridepublic 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:

• Count the number of even item in the list.
• Count the number of prime item in the list.
• Add item X before the first even element in the list.
• Find the maximum number in the list.
• (*) Reverse the list without using temporary list.
• (*) Sort the list in ascending order.