|
|
|
Singly linked list implementation
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:
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
|
|
|
|
|
|
|
|
List of Linked List Data Structure Examples
- Singly linked list implementation in java
- Doubly linked list in Java
|
|
|
Difference between Enumeration and Iterator
The functionality of Enumeration and the Iterator are same. You can get remove()
from Iterator to remove an element, while while Enumeration does not have remove()
method. Using Enumeration you can only traverse and fetch the objects, where as using
Iterator we can also add and remove the objects. So Iterator can be useful if you want
to manipulate the list and Enumeration is for read-only access.
There is a great difference between worry and concern. A worried person sees a problem, and a concerned person solves a problem.
-- Harold Stephens
|
