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
122public class LinkedList {
private Node head;
private int length;
/* No hace falta crear un constructor
* que no tome parametros que ponga
* head y length a valores iniciales
* (null, y 0 respectivamente) debido
* a §4.12.5 de la especificación de java.
*/
/* En cualquier caso, se haría de esta
* forma:
* public LinkedList() {
* this.head = null;
* this.lentgh = 0;
* }
*/
/* Devuelve el numero de elementos
* de la linked list
*/
public int length() {
return length;
}
public boolean has(int elem) {
return find(elem) != -1;
}
/* devuelve el elemento en la posicion
* index
*/
public int get(int index) throws ArrayIndexOutOfBoundsException {
return getNode(index).getData();
}
public int ocurrencesOf(int elem) {
int result = 0;
Node currentNode = head;
for(int i = 0; i < length; i++) {
if(currentNode.getData() == elem) {
result++;
}
currentNode = getNode(1,currentNode);
}
return result;
}
public int find(int elem) {
int index = -1;
Node currentNode = head;
for( int i = 0; i < length && index == -1; i++ ) {
if(currentNode.getData() == elem) {
index = i;
}
currentNode = getNode(1,currentNode);
}
return index;
}
public void remove(int elem) {
int index_to_delete = find(elem);
if(index_to_delete == -1) {
return;
}
length--;
if(index_to_delete == 0) {
head = head.getNext();
return;
}
Node backNode = getNode(index_to_delete - 1);
backNode.setNext(getNode(2,backNode));
}
public Node getNode(int index) throws ArrayIndexOutOfBoundsException {
if(index < 0 || index >= length) {
System.err.println("indice fuera de la lista");
throw new ArrayIndexOutOfBoundsException();
}
Node current = head;
for(int i = 0; i < index; i++) {
current = current.getNext();
}
return current;
}
public Node getNode(int index, Node startingNode){
Node current = startingNode;
for(int i = 0; i < index && current.getNext() != null; i++) {
current = current.getNext();
}
return current;
}
public void addFirst(int elem) {
Node newHead = new Node(elem,head);
head = newHead;
length++;
}
public void addLast(int elem) {
Node newEnd = new Node(elem,null);
getNode(length-1).setNext(newEnd);
length++;
}
public String toString() {
String result = "";
for(int i = 0; i < length; i++) {
Node current = getNode(i);
result += "-> Data: " + current.getData() ;
}
return result + " :: length("+length+")";
}
}