forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSinglyLinkedList.java
More file actions
149 lines (130 loc) · 3.26 KB
/
SinglyLinkedList.java
File metadata and controls
149 lines (130 loc) · 3.26 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
/**
* This class implements a SinglyLinked List. This is done
* using SinglyLinkedList class and a LinkForLinkedList Class.
* <p>
* A linked list is similar to an array, it hold values.
* However, links in a linked list do not have indexes. With
* a linked list you do not need to predetermine it's size as
* it grows and shrinks as it is edited. This is an example of
* a singly linked list. Elements can only be added/removed
* at the head/front of the list.
*
* @author yanglbme
*/
class SinglyLinkedList {
/**
* Head refer to the front of the list
*/
private Node head;
/**
* Count of nodes
*/
private int count;
/**
* This method inserts an element at the head
*
* @param x Element to be added
*/
public void insertHead(int x) {
Node newNode = new Node(x);
newNode.next = head;
head = newNode;
++count;
}
/**
* Inserts a new node at a specified position
*
* @param data data to be stored in a new node
* @param position position at which a new node is to be inserted
*/
public void insertNth(int data, int position) {
if (position < 0 || position > count) {
throw new RuntimeException("position less than zero or position more than the count of list");
}
Node node = new Node(data);
Node dummy = new Node(-1);
dummy.next = head;
Node cur = dummy;
for (int i = 0; i < position; ++i) {
cur = cur.next;
}
node.next = cur.next;
cur.next = node;
++count;
}
/**
* This method deletes an element at the head
*
* @return The element deleted
*/
public Node deleteHead() {
if (isEmpty()) {
throw new RuntimeException("The list is empty!");
}
Node temp = head;
head = head.next;
--count;
return temp;
}
/**
* Checks if the list is empty
*
* @return true is list is empty
*/
public boolean isEmpty() {
return count == 0;
}
/**
* Prints contents of the list
*/
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.value + " ");
current = current.next;
}
System.out.println();
}
/**
* Main method
*
* @param args Command line arguments
*/
public static void main(String args[]) {
SinglyLinkedList myList = new SinglyLinkedList();
assert myList.isEmpty();
myList.insertHead(5);
myList.insertHead(7);
myList.insertHead(10);
myList.display(); // 10 -> 7 -> 5
myList.deleteHead();
myList.display(); // 7 -> 5
myList.insertNth(11, 2);
myList.display(); // 7 -> 5 -> 11
}
}
/**
* This class is the nodes of the SinglyLinked List.
* They consist of a value and a pointer to the node
* after them.
*
* @author yanglbme
*/
class Node {
/**
* The value of the node
*/
int value;
/**
* Point to the next node
*/
Node next;
/**
* Constructor
*
* @param value Value to be put in the node
*/
Node(int value) {
this.value = value;
}
}