-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedListClient.java
189 lines (162 loc) · 4.67 KB
/
LinkedListClient.java
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
class ListNode{
public ListNode next;
public int data;
// Creates an empty node.
public ListNode(){
next = null;
data = Integer.MIN_VALUE;
}
// Creates a node storing the specified data.
public ListNode (int data){
next = null;
this.data = data;
}
// Returns the node that follows this one.
public ListNode getNext(){
return next;
}
// Sets the node that follows this one.
public void setNext (ListNode node){
next = node;
}
// Returns the data stored in this node.
public int getData(){
return data;
}
// Sets the data stored in this node.
public void setdata (int elem){
data = elem;
}
// Sets the data stored in this node.
public String toString (){
return Integer.toString(data);
}
}
class LinkedList {
// This is the only field of the class. It holds the head of the list
ListNode head;
// This class has a default constructor:
public LinkedList() {
length = 0;
}
// Length of the linked list
private int length = 0;
// Insert a node at the beginning of the list
public void insertAtBegin(ListNode node) {
node.setNext(head);
head = node;
length ++;
}
// Insert a node at the end of the list
public void insertAtEnd(ListNode node) {
if (head == null)
head = node;
else {
ListNode p, q;
for(p = head; (q = p.getNext()) != null; p = q);
p.setNext(node);
}
length ++;
}
// Remove and return the node at the head of the list
public ListNode removeFromBegin() {
ListNode node = head;
if (node != null) {
head = node.getNext();
node.setNext(null);
}
return node;
}
// Remove and return the node at the end of the list
public ListNode removeFromEnd() {
if (head == null)
return null;
ListNode p = head, q = null, next = head.getNext();
if (next == null) {
head = null;
// reduce the length of the list
length-=1;
return p;
}
while((next = p.getNext()) != null) {
q = p;
p = next;
}
q.setNext(null);
// reduce the length of the list
length-=1;
return p;
}
// Remove the value at a given position.
// If the position is less than 0, remove the value at position 0.
// If the position is greater than 0, remove the value at the last position.
public void remove(int position) {
// fix position
if (position < 0) {
position = 0;
}
if (position >= length) {
position = length-1;
}
// if nothing in the list, do nothing
if (head == null)
return;
// if removing the head element...
if (position == 0) {
head = head.getNext();
}
// else advance to the correct position and remove
else {
ListNode temp = head;
for (int i=1; i<position; i+=1) {
temp = temp.getNext();
}
temp.setNext(temp.getNext().getNext());
}
// reduce the length of the list
length -= 1;
}
// Return a string representation of this collection, in the form ["str1","str2",...].
public String toString() {
String result = "[";
if (head == null) {
return result+"]";
}
result = result + head.getData();
ListNode temp = head.getNext();
while (temp != null) {
result = result + "," + temp.getData();
temp = temp.getNext();
}
return result + "]";
}
// Return the current length of the list.
public int length() {
return length;
}
// Find the position of the first value that is equal to a given value.
// The equals method us used to determine equality.
public int getPosition(int data) {
// go looking for the data
ListNode temp = head;
int pos = 0;
while (temp != null) {
if (temp.getData() == data) {
// return the position if found
return pos;
}
pos += 1;
temp = temp.getNext();
}
// else return -1
return Integer.MIN_VALUE;
}
// Size of the list.
public boolean isEmpty(){
return length==0;
}
}
public class LinkedListClient {
public static void main(String[] args) {
}
}