-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLinkedList.java
More file actions
150 lines (122 loc) · 4.22 KB
/
Copy pathLinkedList.java
File metadata and controls
150 lines (122 loc) · 4.22 KB
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
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
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
140
141
142
143
144
145
146
147
148
149
150
package dataStructure;
/*
* Author: Ri Xin Yang
* Date: April 19, 2019
* Desc: This class is the LinkedList data structure as defined by the LinkedListADT interface.
* This acts as a dynamic list using nodes. Note that <T> represents a generic object type.
* This object type needs to be defined when instantiating the linked list.
*/
public class LinkedList<T> implements LinkedListADT<T> {
private ListNode<T> front = null;
private int numberOfNodes = 0;
// Returns true if the linked list has no nodes, or false otherwise.
@Override
public boolean isEmpty() {
return (front == null);
}
// Deletes all of the nodes in the linked list.
// Note: ListNode objects will be automatically garbage collected by JVM.
@Override
public void clear() {
front = null;
numberOfNodes = 0;
}
// Returns the number of nodes in the linked list
@Override
public int size() {
return numberOfNodes;
}
// Adds a node to the front of the linked list.
@Override
public void addFirst(T element) {
front = new ListNode<T>(element, front);
numberOfNodes++;
}
// Add an element to the end of the linked list
@SuppressWarnings("unchecked")
public void addLast(T element) {
if (isEmpty()) {
addFirst(element);
}
else{
ListNode<T> lastNode;
ListNode<T> newNode;
lastNode = front;
// traverse list
while ((lastNode.getNext() != null)) {
lastNode = lastNode.getNext();
}
// create new node and set to last via reference
newNode = new ListNode<T>(element, null);
lastNode.setNext(newNode);
numberOfNodes++;
}
}
// Returns a reference to the data in the first node, or null if the list is empty.
@Override
public T peekFirst() {
if (isEmpty())
return null;
return front.getData();
}
// Removes a node from the front of the linked list (if there is one).
// Returns a reference to the data in the first node, or null if the list is empty.
@Override
@SuppressWarnings("unchecked")
public T removeFirst() {
T tempData;
if (isEmpty())
return null;
tempData = front.getData();
front = front.getNext();
numberOfNodes--;
return tempData;
}
// Removes a node from the end of the linked list (if there is one).
// Returns a reference to the data in the first node, or null if the list is empty.
@SuppressWarnings("unchecked")
public T removeLast() {
T tempData;
ListNode<T> previousNode = null;
ListNode<T> lastNode = null;
if (isEmpty())
return null;
else if (size() == 1)
return removeFirst();
previousNode = front;
lastNode = front.getNext();
// traverse list
while ((lastNode.getNext() != null)) {
previousNode = lastNode;
lastNode = lastNode.getNext();
}
tempData = lastNode.getData();
previousNode.setNext(null);
numberOfNodes--;
return tempData;
}
// Returns true if the linked list contains a certain element, or false otherwise.
@Override
@SuppressWarnings("unchecked")
public boolean contains(T key) {
ListNode<T> searchNode;
searchNode = front;
while ((searchNode != null) && (!key.equals(searchNode.getData()))) {
searchNode = searchNode.getNext();
}
return (searchNode != null);
}
// Return String representation of the linked list.
@Override
@SuppressWarnings("unchecked")
public String toString() {
ListNode<T> node;
String linkedList = "FRONT ==> ";
node = front;
while (node != null) {
linkedList += "[ " + node.getData() + " ] ==> ";
node = node.getNext();
}
return linkedList + "NULL";
}
}