Pages

1/01/2015

Singly LinkList and its Basic operations


Singly LinkList consist of a number of nodes in which each nodes has a next pointer to the following element . The List of the last node in the list is NULL which indicates the end of the List.
Basic operations on a List

Traversing the list.
Inserting an item in to the list.
Deleting a item from the list.


For creating declaration for a link nodes to create linklist.
class Link
{
private int data;
private Link next;
public Link(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Link getNext() {
return next;
}
public void setNext(Link next) {
this.next = next;
}
public void displayLink()
{
System.out.print(getData()+" ");
}
}

Traversing is basically displaying the known nodes.
We also do the same operation for two purposes one is to display the nodes and other is to take size of the entire List.
follow the pointers .
Display the contents of the node or count as they are traversed .
Stop the next pointer points to Null .

creating a method for display list
public void displayList()
{
Link current = first ;
while(current != null )
{
current.displayLink();
current = current.getNext();
}
System.out.println("");
}
}


creating a method for counting the length of the list.
public int listLength()
{
int size = 0;
Link current = first ;
while(current != null )
{
size++;
current = current.getNext() ;
}
return size;
}

Singly List insertion
Inserting a node at the beginning of the list.
Update the next pointer of new node,to point he current node.
Update the head pointer to point he new node .

public void insertFirst(int data)
{
Link newLink = new Link(data);
if (isEmpty())
last = newLink ;
else
newLink.setNext(first);
first = newLink ;
}


Inserting a node at End
New nodes next pointer points to the null .
last nodes pointer pointer points to the new node .

public void insertLast(int data)
{
Link newLink = new Link(data);
if(last == null)
first = newLink ;
else
last.setNext(newLink) ;
last = newLink ;
}


Inserting a node at middle by position.
If we want to insert a element in nth position then we stop at (n-1)th position . The pointer of the n-1 position node points to the nth node ,This node is called position node.
n-1th node points to the new node .
new node points the remaining node .
 public void insertIntermediate(int newnodeData,int position)
{
Link newLink = new Link(newnodeData);
if (first == null )
{
first = newLink ;
}
int size = listLength() ;
if (position > size+1 || position < 1)
{
System.out.println("Position of node to insert is invalid. The valid input is from 1 to "+(size+1));
}
else
{
if (position == 1 )
{
newLink.setNext(first);
first = newLink ;
}
else
{
Link previous = first ;
int count = 1;
while (count < position -1) {
previous = previous.getNext() ;
count++ ;
}
Link current = previous.getNext() ;
newLink.setNext(current);
previous.setNext(newLink);
}
}
}


Singly List Deletion
Deleting first node in Singly Link List.
set first node to fist to first next pointer .
public void deleteFirst()
{
if(isEmpty())
last = null ;
else
first = first.getNext();
}

Deleting last node in Singly link list .
Traverse through the list till reach at previous pointer point to last node .
make the previous node to last and next pointer of previous to null
public void deleteLast()
{
Link previous = first ;
if(last == null) {
} else
{
if(first == last)
{ first = null ;
last = null ;}
else
{
while (previous.getNext() != last ) {
previous = previous.getNext() ;
}
last = previous ;
last.setNext(null);
}
}
}


Deleting intermediate nodes in singly list.
This can be in two methods , one is to find the position and delete the element in the position and second is to delete the node directly .
Traverse through the node till reach the previous position of the element to delete .
one we found the node to be deleted, change the previous nodes next pointer of the node to be deleted.
For deleting element
public void deleteIntermediatebyData(int dataToDelete)
{
Link current = first;
// search for link
Link previous = first;
while(current.getData() != dataToDelete)
{
if(current.getNext() == null)
return ;
// didn’t find it
else
{
previous = current;
// go to next link
current = current.getNext();
}
}
// found it
if(current == first)
// if first link,
first = first.getNext();
else
// otherwise,
previous.setNext(current.getNext());
}

For deleting element by position
 public void deleteIntermediatebyPosition(int position)
{
int size = listLength() ;
if(position < 1 || position > size)
{
System.out.println("Entered position are not valid . The valid inputs are from 1 to "+(size));
}
else
{
if(position == 1)
{
Link current = first.getNext() ;
first = current ;
}
else
{
Link previous = first ;
int count = 1 ;
while (count < (position-1)) {
previous = previous.getNext() ;
count++ ;
}
Link current = previous.getNext() ;
previous.setNext(current);
current = null ;
}
}
}


For full and Executable program SingleLinkListAPP

No comments:

Post a Comment

widget

selenium javascript alert box

This is a easy task to capture javascript based alertbox , /* * To change this license header, choose License Headers in Project Properti...