Implement simple Linked List

Implementation of a simple Linked List basically consist with two classes.
1. Link class
2.LinkedList class

Basically Linked List consist with links which are objects of Link class. A link consists data and a reference variable of type Link which points the next link of the list. A Linked list made of
1.set of  links (objects of Link class) which each and every link points next link (and contains data)
2. a variable points the first link of the list.

Linked List class has a variable of type Link to point the first link of the list. Unlike arrays links doesn't have indexes. So accessing a link is done by go through the relationships. For example assume you are in a classroom. You need to find a student called 'Emma'.But you don't know exactly the location of Emma. Then     you ask your neighbor 'can you tell me where Emma is'. Then he says 'I think Ralph know where Emma is'. Then you ask Ralph and so on.

class Link
{
public int iData;               // data
public double dData;                // data
public Link next;                 // reference to next link


public Link(int id, double dd)     {             // constructor
       iData = id;
      dData = dd;
          }

}

 class LinkList
{
private Link first;

public void LinkList()   {           // constructor
       first = null;         // no items on list yet
      }
}

Inserting and deleting
First we look at inserting new link at the beginning of the list. It is done by two steps.
1.new link's next variable points to the first link of the list.
2.first variable of LinkList points to the new link.



 class LinkList
{
private Link  first;

public void LinkList()  {
       first = null;

      }

public void  insertFirst(int id,  double dd)
Link  newLink = new  Link(id, dd);  //Creating a new link of type Link

newLink.next = first;     // 1.The next variable of new link points to the first link of the list.

first = newLink;      // 2.point first variable of LinkedList to new link. 
}

}

Delete the first link.
Before delete, the list is like follow
Delete first variable can be done in two steps.
1.assign first link to a temp variable
2.point first variable in Linked List to first.next 

 class LinkList
{
private Link  first;

public void LinkList()  {
       first = null;

      }

public void  insertFirst(int id,  double dd)
Link  newLink = new  Link(id, dd);  
newLink.next = first;    
first = newLink;     
}


public Link deleteFirst() {
Link temp = first;                          //1. assign first link to a temp variable
first = first.next;                    // 2.point first variable in Linked List to first.next 
return temp;                 // return deleted link
}


}

Let's look at a complete java code of a simple linked list
1.Link class
2.Linked List class
3.Runner class and output

Find a specific Link by a key value
Delete a link by a key value



.............to be continued.............

1 comment:

  1. wooow it looks great :) thanks for sharing this with me ... i have keeping my eyes on these notes :) really amazing ........

    ReplyDelete