Java example- Linked list data structure

Linked list data structure

This is the Java example code for a linked list data structure. If you are not sure about the linked list, i recommend you to visit this tutorial:

Algorithm and Data Structure  

class ListNode<T>{ //T is a generic type.
ListNode(T elem) { val = elem; prev = next = null; }
public T val; //node data
public ListNode<T> prev;//previous link
public ListNode<T> next;//next link
}
public class LinkedList<T>{
LinkedList() { pfirst = plast = null; }
protected ListNode<T> pfirst; //stores the first element
protected ListNode<T> plast; //stores the last element

//insert item
public void insert(T val, int pos)
{
ListNode<T> newnode = new ListNode<T>(val);
//empty list
if (pfirst == null && plast == null)
{
pfirst = newnode;
plast = newnode;
System.out.println("Inserted:"+newnode.val);
}
//Insert at the beginning of the list
else if (pos == 1)
{
ListNode<T> f;
f = pfirst;
pfirst = newnode;
pfirst.next = f;
f.prev = pfirst;
System.out.println("Inserted:"+newnode.val);
}
//Insert in the middle of the list
else if (pos > 1 && pos < countitem())
{
ListNode<T> ta;
ta = pfirst;
for (int t = 1; t < pos; t = t + 1) { ta = ta.next; }
newnode.next = ta;
newnode.prev = ta.prev;
ta.prev.next = newnode;
ta.prev = newnode;
System.out.println("Inserted:"+newnode.val);
}
else if (pos == countitem() + 1)
{

newnode.next = null; //The next link of the item is null.
plast.next = newnode;
newnode.prev = plast;
plast = newnode;
System.out.println("Inserted:"+newnode.val);

}
else System.out.println("Invalid position!");


}

//delete item

public void delete(int pos)
{
if (countitem() > 0)
{ //make sure the list is not empty.
ListNode<T> temp;
T delitem;
if (pos == 1)
{//delete the first item
temp = pfirst;
pfirst = pfirst.next;
pfirst.prev = null;
delitem=temp.val;
temp = null;
System.out.println("Deleted: "+delitem);


}

else if (pos > 1 && pos < countitem())
{//delete middle item
temp = pfirst;
int i;
for (i = 1; i < pos; i = i + 1) { temp = temp.next; }
temp.prev.next = temp.next;
temp.next = temp.prev;
delitem=temp.val;
temp = null;
System.out.println("Deleted: "+delitem);

}
else if (pos == countitem())
{//delete the last item

temp = plast;
plast = plast.prev;
plast.next = null;
delitem=temp.val;
temp = null;
System.out.println("Deleted: "+delitem);

}

else System.out.println("Invalid position!");

}

else System.out.println("No item found");

}



//count the number of items in the list
public int countitem()
{
ListNode<T> i;
int t = 0;
for (i = pfirst; i != null; i = i.next)
{
t = t + 1;
}
return t;
}

//show all items
public void showall()
{
ListNode<T> t;
if (countitem() > 0)
{
System.out.println("All items in the list:");
for (t = pfirst; t != null; t = t.next)
{

System.out.println(t.val);
}
}
else System.out.println("No item found!");
}



public static void main(String[] args){

LinkedList<Integer> mylist=new LinkedList<Integer>();
mylist.insert(100,1);
mylist.insert(101,2);
mylist.insert(102,3);
mylist.delete(3);
mylist.showall();
System.out.println("----------------------------------------");
}

}

Note: In the Java example code above, we created generic classes ListNode(ListNode<T>) and LinkedList(LinkedList<T>). Generic classes are classes that take type parameter(T). By doing so, we can create a linkedlist object to store any type of value(Integer, Double, String,etc) .