I have discussed data structure Stack, Queue and variations
of Queue in last post. Today we will discuss commonly used data structure
Linked list. As it is implied from name, it is a list of data linked with each
other by some mean. Stack and Queues can be implemented by array or linked
lists.
Array and Linked list have their own advantages and
disadvantages
Disadvantages of Array which are addressed by Linked list
- Arrays are of fixed size whereas linked list has no size limit.
- Insertion and deletion is slow in Array, as many items are shifted to create the place for new item or to fill the due to deletion. These activities are fast in linked list.
What is linked list?
Linked list contains data and reference to next link. Linked
list is set of data linked to one another. Linked list provides set of functions to
iterate over the linked list, to delete, insert data.
Java Code of Data item in linked list
public class Link {
public int data; //this can be any
data or reference to any data
public Link next; // refer to next
item in linked list
public Link(int newData) {
this.data = newData;
}
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 displayData()
{
System.out.println(this.data);
}
}
“next” value is null,
when it is the last item in linked list.
I will describe simple linked list, this has very limited
function to carry out on Linked list. Following are the action which can be
carried out on simple linked list
- Insert data at the beginning of linked list
- Delete data at the beginning of linked list
- View all the data in the list.
Java code for Linked list application class
class LinkList
{
private Link first; // refer to
first link in the list
public LinkList()
{
first = null;
}
public boolean isEmpty()
{
return (first==null);
}
public void insertFirst(int id,
double dd)
{
Link newLink = new
Link(id);
newLink.next = first;
first = newLink;
}
public Link deleteFirst()
{
Link temp = first;
first = first.next;
return temp;
}
public void displayList()
{
Link current = first;
while(current != null)
{
current.displayData();
current =
current.next;
}
}
}
Other variations of linked list
Double ended list: It
is same as ordinary linked list with an additional feature: an additional reference
to last link. This gives it a benefit of adding data item directly at the end
of the list rather than iterating over whole list and then inserting the data.
Doubly linked list: This is also same as ordinary linked
list, but it has an additional feature which let you move in both directions.
This improves traversal activity required in some of the activity.
No comments:
Post a Comment