Singly Linked Lists are a type of data structure. It is a type of list. In a singly linked list each node in the list stores the contents of the node and a pointer or reference to the next node in the list. It does not store any pointer or reference to the previous node. It is called a singly linked list because each node only has a single link to another node. To store a single linked list, you only need to store a reference or pointer to the first node in that list. The last node has a pointer to nothingness to indicate that it is the last node.
Here is the pictorial view of singly linked list:
Here is the pictorial view of inserting an element in the middle of a singly linked list:
Here is the pictorial view of deleting an element in the middle of a singly linked list:
Below shows the java implementation of singly linked list:
|
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 150 151 152 153 154 155 156 157 158 |
package com.java2novice.ds.linkedlist; public class SinglyLinkedListImpl<T> { private Node<T> head; private Node<T> tail; public void add(T element){ Node<T> nd = new Node<T>(); nd.setValue(element); System.out.println("Adding: "+element); /** * check if the list is empty */ if(head == null){ //since there is only one element, both head and //tail points to the same object. head = nd; tail = nd; } else { //set current tail next link to new node tail.setNextRef(nd); //set tail as newly created node tail = nd; } } public void addAfter(T element, T after){ Node<T> tmp = head; Node<T> refNode = null; System.out.println("Traversing to all nodes.."); /** * Traverse till given element */ while(true){ if(tmp == null){ break; } if(tmp.compareTo(after) == 0){ //found the target node, add after this node refNode = tmp; break; } tmp = tmp.getNextRef(); } if(refNode != null){ //add element after the target node Node<T> nd = new Node<T>(); nd.setValue(element); nd.setNextRef(tmp.getNextRef()); if(tmp == tail){ tail = nd; } tmp.setNextRef(nd); } else { System.out.println("Unable to find the given element..."); } } public void deleteFront(){ if(head == null){ System.out.println("Underflow..."); } Node<T> tmp = head; head = tmp.getNextRef(); if(head == null){ tail = null; } System.out.println("Deleted: "+tmp.getValue()); } public void deleteAfter(T after){ Node<T> tmp = head; Node<T> refNode = null; System.out.println("Traversing to all nodes.."); /** * Traverse till given element */ while(true){ if(tmp == null){ break; } if(tmp.compareTo(after) == 0){ //found the target node, add after this node refNode = tmp; break; } tmp = tmp.getNextRef(); } if(refNode != null){ tmp = refNode.getNextRef(); refNode.setNextRef(tmp.getNextRef()); if(refNode.getNextRef() == null){ tail = refNode; } System.out.println("Deleted: "+tmp.getValue()); } else { System.out.println("Unable to find the given element..."); } } public void traverse(){ Node<T> tmp = head; while(true){ if(tmp == null){ break; } System.out.println(tmp.getValue()); tmp = tmp.getNextRef(); } } public static void main(String a[]){ SinglyLinkedListImpl<Integer> sl = new SinglyLinkedListImpl<Integer>(); sl.add(3); sl.add(32); sl.add(54); sl.add(89); sl.addAfter(76, 54); sl.deleteFront(); sl.deleteAfter(76); sl.traverse(); } } class Node<T> implements Comparable<T> { private T value; private Node<T> nextRef; public T getValue() { return value; } public void setValue(T value) { this.value = value; } public Node<T> getNextRef() { return nextRef; } public void setNextRef(Node<T> ref) { this.nextRef = ref; } @Override public int compareTo(T arg) { if(arg == this.value){ return 0; } else { return 1; } } } |
Output:
Adding: 3
Adding: 32
Adding: 54
Adding: 89
Traversing to all nodes..
Deleted: 3
Traversing to all nodes..
Deleted: 89
32
54
76