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) .

 



HTML Comment Box is loading comments...



This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.