How to create a LinkedList in Java.
I am assuming that everyone knows what is linked list? Click here to know more about linked list.
Functionality of this program:
- Create a Node class which will represent the Singly Linked List.
- Value at linked list node
- Next Node
- Singly Linked List Implementation Class
- Head: First node of the linked list. Initial value is null.
- Tail: Last node of the linked list. Initial value is null.
- add Method: This method adds a node at the end of the linked list.
- addAfter Method: adds a node after a given node.
- deleteAfter Method: deletes a node after a given node.
- deleteFront Method: deletes the head node which is also is the starting point of the linked list. After this method second node of the linked list becomes the head node.
- reverse Method: revers the given linked list.
- traverse Method: prints the full linked list.
- Result of this program:
1: package com.research.list.linkedlist;
2: public class Node<T> implements Comparable<T> {
3: private T value;
4: private Node<T> nextRef;
5: public T getValue() {
6: return value;
7: }
8: public void setValue(T value) {
9: this.value = value;
10: }
11: public Node<T> getNextRef() {
12: return nextRef;
13: }
14: public void setNextRef(Node<T> nextRef) {
15: this.nextRef = nextRef;
16: }
17: public int compareTo(T arg) {
18: if(arg == this.value){
19: return 0;
20: } else {
21: return 1;
22: }
23: }
24: }
1: package com.research.list.linkedlist.singly;
2: import org.springframework.stereotype.Component;
3: import com.research.list.linkedlist.Node;
4: public class SinglyLinkedListImpl<T> {
5: Node<T> head;
6: Node<T> tail;
7: public void add(T element){
8: Node<T> node = new Node<T>();
9: node.setValue(element);
10: if(head == null){
11: head = node;
12: tail = node;
13: } else {
14: tail.setNextRef(node);
15: tail = node;
16: }
17: }
18: public void addAfter(T element, T after){
19: Node<T> node = new Node<T>();
20: node.setValue(element);
21: Node<T> tmp = head;
22: Node<T> refNode = null;
23: while(true){
24: if(tmp == null)
25: break;
26: if(tmp.compareTo(after) == 0){
27: refNode=tmp;
28: break;
29: }
30: tmp = tmp.getNextRef();
31: }
32: if(refNode != null){
33: node.setNextRef(tmp.getNextRef());
34: if(tmp.compareTo(tail.getValue()) == 0)
35: tail=node;
36: tmp.setNextRef(node);
37: }
38: }
39: public void deleteFront(){
40: if(head == null){
41: System.out.println("UnderFlow");
42: } else{
43: Node<T> tmp = head;
44: head = tmp.getNextRef();
45: if(head == null){
46: tail = null;
47: }
48: }
49: }
50: public void deleteAfter(T after){
51: Node<T> tmp = head;
52: Node<T> refNode = null;
53: while(true){
54: if(tmp == null)
55: break;
56: if(tmp.compareTo(after) == 0){
57: refNode=tmp;
58: break;
59: }
60: tmp=tmp.getNextRef();
61: }
62: if(refNode != null){
63: tmp = refNode.getNextRef();
64: refNode.setNextRef(tmp.getNextRef());
65: if(refNode.getNextRef() == null){
66: tail = refNode;
67: }
68: }
69: }
70: public void reverse(){
71: Node<T> currentNode = head;
72: Node<T> nextNode = null;
73: Node<T> previousNode = null;
74: while(currentNode != null){
75: nextNode = currentNode.getNextRef();
76: currentNode.setNextRef(previousNode);
77: previousNode = currentNode;
78: currentNode = nextNode;
79: }
80: head = previousNode;
81: }
82: public void traverse(){
83: Node<T> tmp = head;
84: while(true){
85: if(tmp == null)
86: break;
87: System.out.print(tmp.getValue()+",");
88: tmp=tmp.getNextRef();
89: }
90: System.out.println("");
91: }
92: public static void main(String[] args) {
93: SinglyLinkedListImpl<Integer> linkedList = new SinglyLinkedListImpl<Integer>();
94: linkedList.add(3);
95: linkedList.add(45);
96: linkedList.add(12);
97: linkedList.add(32);
98: linkedList.add(49);
99: linkedList.add(98);
100: linkedList.add(90);
101: linkedList.add(42);
102: linkedList.traverse(); // 1: Traverse - initial Linked List
103: linkedList.addAfter(21, 90);
104: linkedList.traverse(); // 2: Traverse - after adding 21 after 90
105: linkedList.addAfter(67, 42);
106: linkedList.traverse(); // 3: Traverse - after adding 67 after 42
107: linkedList.deleteAfter(49);
108: linkedList.traverse(); // 4: Traverse - after deleting number after 49
109: linkedList.deleteFront();
110: linkedList.traverse(); // 5: Traverse - after deleting front number from linked list
111: linkedList.reverse();
112: linkedList.traverse(); // 6: Traverse - after reversing the linked list
113: }
114: }
No comments:
Post a Comment