Skip to content

Commit f1c0709

Browse files
honokaBiuhonokaBiu
committed
LinkedList
1 parent 8758eda commit f1c0709

File tree

2 files changed

+317
-0
lines changed

2 files changed

+317
-0
lines changed

‎group20/1040154728/1040154728Learning/src/SinglyLinkedList/LinkedList0.java

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package SinglyLinkedList;
2+
3+
/**
4+
* Created by Honoka on 2/16/2017.
5+
*/
6+
public class LinkedList0 {
7+
//Node class represents a list node
8+
private class Node
9+
{
10+
String value;
11+
Node next;
12+
/**
13+
* Constructor
14+
* @param val The element to store in this node.
15+
* @param n The reference to the next node.
16+
*/
17+
Node (String val, Node n)
18+
{
19+
value = val;
20+
next = n;
21+
}
22+
23+
/**
24+
* Constructor
25+
* @param val The element to store in this node.
26+
*/
27+
Node(String val)
28+
{
29+
value = val;
30+
next = null;
31+
}
32+
}
33+
//Reference to the first node in the list
34+
private Node first = null;
35+
/**
36+
* Constructor
37+
* Builds a linked list
38+
*/
39+
public LinkedList0()
40+
{
41+
//test
42+
first = new Node("Apple");
43+
first.next = new Node("Peach");
44+
first.next.next = new Node("Kiwi");
45+
first = new Node("Blueberry",first);
46+
47+
//Using an array to add elements into list
48+
String[] fruits = {"Banana", "Cherry"};
49+
for (String f : fruits)
50+
{
51+
first = new Node(f, first);
52+
}
53+
}
54+
/**
55+
* print method
56+
* traverses the list and prints all elements
57+
*/
58+
public void print()
59+
{
60+
Node reference = first;
61+
while(reference != null)
62+
{
63+
System.out.println(reference.value + " ");
64+
reference = reference.next;
65+
}
66+
}
67+
68+
//Main test method
69+
public static void main(String [] args)
70+
{
71+
LinkedList0 list = new LinkedList0();
72+
System.out.println("The elements inside this list are ");
73+
list.print();
74+
}
75+
}

‎group20/1040154728/1040154728Learning/src/SinglyLinkedList2/LinkedList1.java

Lines changed: 242 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,242 @@
1+
package SinglyLinkedList2;
2+
/**
3+
* Created by Honoka on 2/16/2017.
4+
*/
5+
public class LinkedList1 {
6+
private class Node
7+
{
8+
String value;
9+
Node next;
10+
11+
Node(String val, Node n)
12+
{
13+
value = val;
14+
next = n;
15+
}
16+
Node(String val)
17+
{
18+
//Call the other(daddy(or sister(whatever))) constructor.
19+
this(val, null);
20+
}
21+
}
22+
23+
private Node first; // head
24+
private Node last; //the last element in list
25+
26+
public LinkedList1()
27+
{
28+
first = null;
29+
last = null;
30+
}
31+
32+
/**This method checks to see
33+
* if the list is empty
34+
* @return true if list is empty
35+
*/
36+
public boolean isEmpty()
37+
{
38+
return first == null;
39+
}
40+
41+
/**
42+
* size method returns the length of the list
43+
* @return The number of the elements in the list
44+
*/
45+
public int size()
46+
{
47+
int counter = 0;
48+
Node p = first;
49+
while (p != null)
50+
{
51+
counter ++;
52+
p = p.next;
53+
}
54+
return counter;
55+
}
56+
57+
/**
58+
* add method add an element to the end of the list
59+
* @param element the value to add
60+
*/
61+
public void add(String element)
62+
{
63+
if (isEmpty())
64+
{
65+
//Obviously, add the element to the first position in the list
66+
first = new Node(element);
67+
last = first;
68+
}
69+
else
70+
{
71+
//add to the end of existing list
72+
last.next = new Node(element);
73+
last = last.next;
74+
}
75+
}
76+
77+
/**
78+
* add method, or you might call it insert method since it can
79+
* add element to a specific position
80+
* @param index The position at which to add the element
81+
* @param element you should know what is this
82+
*/
83+
public void add (int index, String element)
84+
{
85+
if (index < 0 || index > size())
86+
{
87+
String message = String.valueOf(index);
88+
throw new IndexOutOfBoundsException(message);
89+
}
90+
91+
//index is at least 0
92+
if(index == 0)
93+
{
94+
//new element add to the head
95+
first = new Node(element, first);
96+
if (last == null)
97+
{
98+
last = first;
99+
}
100+
return;
101+
}
102+
//set a reference predecessor to point to the node that
103+
//will be the predecessor of the new node
104+
Node predecessor = first;
105+
for (int k = 1; k <= index - 1; k++)
106+
{
107+
predecessor = predecessor.next;
108+
}
109+
//Splice in a node containing the new element
110+
predecessor.next = new Node(element, predecessor.next);
111+
112+
//if there is a new last element
113+
if(predecessor.next.next == null)
114+
last = predecessor.next;
115+
}
116+
117+
/**
118+
* toString method, like print method, hopefully it will display the contents of the list
119+
* @return say something I'm giving up on you(
120+
*/
121+
public String toString()
122+
{
123+
StringBuffer strBuilder = new StringBuffer();
124+
//Use p to walk down the list
125+
Node p = first;
126+
while (p != null)
127+
{
128+
strBuilder.append(p.value + "\n");
129+
p = p.next;
130+
}
131+
return strBuilder.toString();
132+
}
133+
134+
/**
135+
* remove method removes the element with the position you want
136+
* @param index the position of the element that you want to remove
137+
* @return the removed element
138+
*/
139+
public String remove (int index)
140+
{
141+
/* Index out of bounds */
142+
if (index < 0 || index >= size())
143+
{
144+
String message = String.valueOf(index);
145+
throw new IndexOutOfBoundsException(message);
146+
}
147+
String element = null;
148+
if(index == 0)
149+
{
150+
//Removal of first item in the list
151+
element = first.value;
152+
first = first.next;
153+
if (first == null)
154+
{
155+
last = null;
156+
}
157+
}
158+
else
159+
{
160+
/* find the predecessor of the element to be removed */
161+
Node predecessor = first;
162+
163+
/* Move predecessor forward index - 1 times */
164+
for (int k = 1; k <= index - 1; k++)
165+
{
166+
predecessor = predecessor.next;
167+
/* Store the value to return */
168+
element = predecessor.next.value;
169+
/* Route link around the node to be removed */
170+
predecessor.next = predecessor.next.next;
171+
/* Check if predecessor is now last */
172+
if(predecessor.next == null)
173+
{
174+
last = predecessor;
175+
}
176+
}
177+
}
178+
return element;
179+
}
180+
181+
/**
182+
* The remove method removes an element
183+
* @param element the element to remove
184+
* @return true if the remove succeeded
185+
*/
186+
public boolean remove(String element)
187+
{
188+
if (isEmpty())
189+
{
190+
return false;
191+
}
192+
193+
if (element.equals(first.value))
194+
{
195+
//Removal of first element in the list
196+
first = first.next;
197+
if(first == null)
198+
{
199+
last = null;
200+
}
201+
return true;
202+
}
203+
204+
/* Find the predecessor of the element to remove */
205+
Node predecessor = first;
206+
while (predecessor.next != null &&
207+
!predecessor.next.value.equals(element))
208+
{
209+
predecessor = predecessor.next;
210+
}
211+
/* predecessor.next == null OR predecessor.next.value is element */
212+
if(predecessor.next == null)
213+
{
214+
return false;
215+
}
216+
/* predecessor.next.value is element */
217+
predecessor.next = predecessor.next.next;
218+
219+
/* check if predecessor is now last */
220+
if (predecessor.next == null)
221+
{
222+
last = predecessor;
223+
}
224+
return true;
225+
}
226+
227+
public static void main (String [] args)
228+
{
229+
LinkedList1 testList = new LinkedList1();
230+
testList.add("Apple");
231+
testList.add("Banana");
232+
testList.add(0,"Blueberry");
233+
testList.add(2,"Cherry");
234+
testList.add(4,"Peach");
235+
System.out.println("The list has : ");
236+
System.out.println(testList);
237+
testList.remove("Cherry");
238+
testList.remove(2);
239+
System.out.println("The list has : ");
240+
System.out.println(testList);
241+
}
242+
}

0 commit comments

Comments
 (0)