Linked List

Linked List

• In a linked list, each data item is embedded in a link. A link is an object of a class called something like Link.
• Each Link object contains a reference (usually called next) to the next link in the list.

What is references type ?

• In Java a Link object doesn’t really contain another Link object.

• The next field of type Link is only a reference to another link, not an object.

• A reference is a number that refers to an object. (It’s the object’s address in the computer’s memory.)

   class Link {
       public int iData; // data item (key) 
       public double dData; // data item 
       public Link next; // next link in list
   	
   	// constructor
   	public Link(int id, double dd) { 
   		iData = id; // initialize data
   		dData = dd; // (‘next’ is automatically set to null)
   	}
   	
   	// display ourself
   	public void displayLink() {
   		System.out.print(“{“ + iData + “, “ + dData + “} “);
   	}
   	
   }
  

  
   class LinkList {
       private Link first; // ref to first link on list
  
   	// constructor
   	public LinkList() {
   		first = null; // no items on list yet
   	}
  
   	// true if list is empty
   	public boolean isEmpty() {
   		return (first==null);
   	}
  
   	// insert at start of list
   	public void insertFirst(int id, double dd) {
   		Link newLink = new Link(id, dd); // make new link
   		newLink.next = first; // newLink --> old first
   		first = newLink; // first --> newLink
   	}
  
   	// delete first item
   	public Link deleteFirst() {
   		Link temp = first; // save reference to link
   		first = first.next; // delete it: first-->old next
   		return temp; // return deleted link
   	}
  
   	public void displayList() {
   		System.out.print(“List (first-->last): “);
   		Link current = first; // start at beginning of list
   		while(current != null) // until end of list,
   		{
   			current.displayLink(); // print data
   			current = current.next; // move to next link
   		}
   		System.out.println(“”);
   	}
   	
   }
  

  
  
  

  Linked-List Efficiency

  • Insertion and deletion at the beginning of a linked list are very fast. (O(1))
  • Finding, deleting, or inserting next to a specific item requires searching. (O(N))
  • The linked list is nevertheless faster than array because nothing needs to be moved when an item is inserted or deleted.
  • A linked list uses exactly as much memory as it needs and can expand to fill all of available memory. (The size of an array is fixed when it’s created)