LinkedList Java

Question

Imagine we have to create a Linked list with 5,8 as elements and at first before adding them head should pointed to null. And since 8 is the last element, next of 8 also should point to a null.

How do construct this LinkedList with following code skeleton.

Public class LinkedList {

static private class ListNode { }

Private static ListNode head;

Public static void main (String[] args) {}

}

Answer 1

The following code is simple LinkedList implementation. Some assumptions were taken: it is a singly linked list and it also always inserts a new node at the end of the list. (There was no requirement about being able to insert at specific location or keeping the values sorted in certain order.)

public class LinkedList {

static private class ListNode {

ListNode next;

final int value;

ListNode(int value) {

this.value = value;

}

}

private static ListNode head;

// Method to insert a new ListNode

public void add(int value)

{

// Create a new ListNode with given value.

ListNode node = new ListNode(value);

node.next = null;

// If the list is empty, then make the new ListNode as head.

if (head == null) {

head = node;

} else {

// Otherwise find the last node and insert the node there.

ListNode last = head;

while (last.next != null) {

last = last.next;

}

last.next = node;

}

}

public static void print() {

ListNode node = head;

while (node != null) {

System.out.print(node.value + " ");

node = node.next;

}

}

public static void main (String[] args) {

LinkedList list = new LinkedList();

list.add(5);

list.add(8);

list.print();

}

}

Answer 2

Unless you are keeping a counter, the node containing the 8 should have it's next pointer equal to null.

It is recommended to do both: keep a count AND ensure the last node of the list has it's next pointer equal to null.

The following code does just that...

Not included in the code is a method in class LinkedList the DELETES a node.

Since we are INSERTING nodes at the end, where we delete them from makes a difference in

the data structure....

In this case, if we delete from the HEAD, then we have a QUEUE... first in , first out

if we delete from the TAIL, then we have a STACK... last in first out

If you want to be able to insert/delete from/to ANY position in the list, then the code becomes much more complicated.... in this case it is recommended to just abandon the list node strategy and use an array, where insertions and deletes to/from any position are much easier

Also, if you want a SORTED list, then insertions are done per sort order. You will need the Insertion Sort instead.

I made it a GENERIC list node, of type Object so any type of data object can be stored, not just integers. You can store integers, decimals, string, and even entire data record objects in the list; the data type need not be the same per node.

Here's the code of what you have asked this far:

//ListNode.java

class ListNode

{

private Object data;

private ListNode next;

ListNode( Object Data)

{

this.data = Data;

this.next = null;

}

public void SetData ( Object Data)

{

this.data = Data;

}

public Object GetData() { return(data); }

public void SetNext( ListNode nextObj)

{

this.next = nextObj;

}

public ListNode GetNext() { return(next); }

}

//LinkedList.java

class LinkedList

{

private ListNode head;

private ListNode tail;

private ListNode mid;

private int count;

LinkedList()

{

head=tail=mid = null;

count = 0;

}

public int GetCount() { return(count); }

public boolean IsEmpty() { return(count==0); }

public void InsertAddnew ( Object Data)

{

if (count==0)

{

head = new ListNode(Data);

head.SetNext(null);

mid = tail = head;

count = 1;

}

else

{

tail.SetNext( new ListNode(Data));

tail = tail.GetNext();

count++;

if ((count%2)==1)

{

mid = mid.GetNext();

}

}

}

public ListNode IndexerGetIndexAt (int iIndexPos)

{

ListNode listNodeReturn = null;

if ((iIndexPos>=0) && (iIndexPos<count))

{

listNodeReturn = head;

for (int iLoop=0; iLoop<iIndexPos; iLoop++)

{

listNodeReturn = listNodeReturn.GetNext();

}

}

return(listNodeReturn);

}//indexerGetIndexAt

public static void main(String args[])

{

int iNum1=3; int iNum2=5;

Integer intObj = new Integer(iNum1);

LinkedList myLinkedList = new LinkedList();

myLinkedList.InsertAddnew( (Object) intObj);

intObj = new Integer(iNum2);

myLinkedList.InsertAddnew( (Object) intObj);

int iRecordCount = myLinkedList.GetCount();

System.out.println(" There are " + iRecordCount + " items in the list....\n They are: \n");

for (int iLoop=0; iLoop<iRecordCount; iLoop++)

{

ListNode listNode = myLinkedList.IndexerGetIndexAt(iLoop);

intObj = (Integer) listNode.GetData();

System.out.println(intObj.intValue());

}

}

}