implementing simple linked list (java)
This program is about implementing simple linked list data structure.
If you do not know what a linked list is, please read more here.
If you do not know what a linked list is, please read more here.
this program consists of three classes:
- ListNode.java: represents the nodes of the linked list.
- A node has an integer value and a pointer to the next node.
- ListHead.java: represents the root/head node of the whole linked list.
- The head node is the first node of the linked list
- Main.java: it has the main method.
package structure:
This program should create a linked list and print it like this:
(4)->(5)->(3)->(1)->(2)->null
And should sort the list with the bubble sort algorithm.
(1)->(2)->(3)->(4)->(5)->null
if you do not know what the bubble sort algorithm is, please read more here.
This program should also create a linked list by passing an array as a parameter to the constructor method.
e.x int arr = {1, 2, 3, 4, 5};
ListHead l = new ListHead(arr); //==> (1)->(2)->(3)->(4)->(5)->null
📢Recommended: Please try to implement the program on your own first, before looking at the code down below.
______________________________________________________
🎁Code:
1. ListNode class:
package simple_linked_list.model;
public class ListNode {
private int value;
private ListNode next = null;
public ListNode(int value, ListNode next) {
this.value = value;
this.next = next;
}
public ListNode(int value) {
this(value, null);
}
public ListNode() {
this(0);
}
public void setValue(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public void setNext(ListNode next) {
this.next = next;
}
public ListNode getNext() {
return next;
}
}
2. ListHead class:
package simple_linked_list.model;
public class ListHead {
private ListNode head;
public ListHead(ListNode head) {
this.head = head;
}
public ListHead(int[] arr) {
if (arr.length < 1) return;
this.head = new ListNode(arr[0],null); // the head of the linked list
ListNode tmp = this.head; //to avoid moving the pointer from the head node
for(int i = 1; i < arr.length; i++) {
ListNode next = new ListNode(arr[i],null);// create the new node
tmp.setNext(next); // link it with the previous node
tmp = tmp.getNext(); //update where the pointer is pointing to
}
}
public void bubbleSort() {
if (this.head == null) return;
int listSize = this.getSize();
for(int i = 0; i < listSize-1; i++) {
ListNode tmp = this.head;
for(int j = 0; j < listSize-1-i; j++, tmp = tmp.getNext())
if(tmp.getValue() > tmp.getNext().getValue()) {
int holdBigValue = tmp.getValue();
tmp.setValue(tmp.getNext().getValue());
tmp.getNext().setValue(holdBigValue);
}
}
}
public int getSize() {
if (this.head == null) return 0;
int size = 0;
for(ListNode tmp = this.head; tmp != null; tmp = tmp.getNext())
size += 1;
return size;
}
@Override
public String toString() {
String s = "";
for(ListNode tmp = this.head; tmp != null; tmp = tmp.getNext())
s += "("+ String.valueOf(tmp.getValue()) + ")->";
s += "null";
return s;
}
}
3. Main class:
package simple_linked_list;
import simple_linked_list.model.*; // to import all classes in this package.
import static java.lang.System.out;
class Main {
public static void main(String[] args) {
int[] arr = {50, 60, 20, 10, 30, 40};
ListHead l1 = new ListHead(arr);
out.println("list1 : " + l1);
ListHead l2 = new ListHead(
new ListNode(4,
new ListNode(5,
new ListNode(3,
new ListNode(1,
new ListNode(2,null) ))))
);
out.println("list2 : " + l2);
out.println("After sorting: " );
l1.bubbleSort();
l2.bubbleSort();
out.println("list1 : " + l1);
out.println("list2 : " + l2);
}
}
output:
list1 : (50)->(60)->(20)->(10)->(30)->(40)->null
list2 : (4)->(5)->(3)->(1)->(2)->null
After sorting:
list1 : (10)->(20)->(30)->(40)->(50)->(60)->null
list2 : (1)->(2)->(3)->(4)->(5)->null
______________________________________________________
Comments
Post a Comment