Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data structures, including stacks, queues, associative arrays, and symbolic expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.
The principal benefit of a linked list over a conventional array is that the list elements can easily be added or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.
On the other hand, simple linked lists by themselves do not allow random access to the data other than the first node's data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list (assuming that the last node is not maintained as separate node reference in the list structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted may require scanning most or all of the list elements.
 |
| A linked list whose nodes contain two fields: an integer value and a link to the next node |
Now let implement it in java, first we need a class of which we want to make links in the list we call it, say Link, below is the code to that class
class Link{
private String data;
private int id;
private Link next;
/**
* @return the data
*/
public String getData() {
return data;
}
/**
* @param data the data to set
*/
public void setData(String data) {
this.data = data;
}
/**
* @return the id
*/
public int getId() {
return id;
}
/**
* @param id the id to set
*/
public void setId(int id) {
this.id = id;
}
/**
* @return the next
*/
public Link getNext() {
return next;
}
/**
* @param next the next to set
*/
public void setNext(Link next) {
this.next = next;
}
public void printData(){
System.out.println(id+" => "+data);
}
}
in the class we make three data members
id of type
int,
data of type
String and the last member
next, focus on its data type it is
Link itself, this is because we will store the reference of the next
Link in
next data member using its assessor method.
Now create a class in which we make the singly link list using the Link class we just made.
class LinkList {
private Link first;
public LinkList(){
first=null;
}
public void addLink(int id, String data){
Link link=new Link();
link.setId(id);
link.setData(data);
link.setNext(first);
first=link;
//first.printData();// un-comment this line to see what data is added
}
public void printList(){
Link currentLink=first;
System.out.println("Printing List:");
if(currentLink==null){
System.out.println("List is Empty, Consider adding elements.");
return;
}
while(currentLink!=null){
currentLink.printData();
currentLink=currentLink.getNext();
}
}
public static void main(String []nix){
LinkList linklist=new LinkList();
linklist.printList();
linklist.addLink(1, "val1");
linklist.addLink(2, "val2");
linklist.addLink(3, "val3");
linklist.addLink(4, "val4");
linklist.printList();
}
}
in this class we made two methods first method addLink add a new link at the head of the previous node, line
link.setNext(first); set the existing reference of the link list to the next of the new link object and
first=link; make the first reference to the newly created link, hence we can add any link at the head of the list. Second method, printList() simply iterate through all the "link" objects in the link list
