What are Linked Lists?

Linked lists are data structures in which each data element has a link or reference to the next data element.

Each data item in a linked list is embedded in a link, which is an object of a class called Link. Link contains the data item and in addition contains a reference to the next link object in the data structure.

Unlike arrays, the data elements in linked lists cannot be accessed directly using an index. The only way to access an element in a linked list is to traverse link by link until you get to the element.

Write a Link class.

A link class contains the data item and a reference to the next data element. Below code snippet is a link class written in Java programming language containing a data element of type int.

class Link {
 //data item
 public int intData;
 //reference to next link
 public Link next;

 public Link(int data) {
  this.intData = data;
 }
}

Write a LinkedList class with method to insert an item in the first position of the LinkedList.

A LinkedList class contains a reference to the first link on the list. Rest of the data items of the linked list are retrieved by using the first item.

Pseudocode
1. Create a new Link link1 that has to be inserted at the first position of the LinkedList.
2. Set link1.next to first.
Set first to link1.

class LinkedList {
  private Link first;
  //constructor
  public void LinkedList() {
  this.first = null;
 }
 //insert an element at start of list
  public void insertFirst(int data) {
    Link link = new Link(data);
    link.next = first;
    first = link;
 }
}

Write a LinkedList class with method to delete the first link in the LinkedList.

A LinkedList class contains a reference to the first link on the list. Rest of the data items of the linked list are retrieved by using the first item.

Pseudocode
1. Set temp to first.
2. Set first to temp.next.

class LinkList {
  private Link first;
  //constructor
  public void LinkList() {
    this.first = null;
  }
  //delete an element from start of list
  public void deleteFirst(){
    Link temp = first;
    first = temp.next;
  }
}

Write a LinkList class with method to search items in the list.

Below Java code snippet includes the find() method added to the LinkList class which searches an item in the linked list.

class LinkList {
 private Link first;
 //constructor
 public void LinkList() {
  this.first = null;
 }
 //search for an item
 public Link find(int key){
  Link current = first;
  while (current.intData!=key) {
    if (current.next==null) {
      return null;
    } else {
      current = current.next;
    }
  }
   return current;
 }
}

Write a LinkList class with method to delete items in the list.

Below Java code snippet includes the delete() method added to the LinkList class which deletes an item in the linked list.

class LinkList {
 private Link first;
 //constructor
 public void LinkList() {
  this.first = null;
 }
 //insert an element at start of list
 public voidinsertFirst(int data) {
  Link link = new Link(data);
  link.next = first;
  first = link;
 }
 //delete an element from start of list
 public void deleteFirst() {
  Link temp = first;
  first = temp.first;
 }
 public Link find(int key) {
  Link current = first;
  while (current.intData!=key) {
    if (current.next==null) {
      return null;
    } else {
      current = current.next;
    }
  }
   return current;
 }
 public Link delete(int key) {
  Link current = first;
  Link previous = first;
  while (current.intData!=key) {
    if current.next==null) {
      return null;
    } else {
      previous = current;
      current = current.next;
    }
  }
  if(current == first) {
    first =first.next;
  } else {
    previous.next = current.next;
  }
   return current;
 }
}

What is the time efficiency of insertion, deletion and searching in linked lists.

Insertion or deletion of an element from the front of the linked list is fast and takes O(1) time. I.e it takes a constant time and is not dependent on the number of data elements in the linked list.

Insertion or deletion of a data element, which is not the first element, takes linear time O(N). I.e the time efficiency linearly depends on the number of elements in the linked list.

Searching for an element in the linked list takes linear time ON(N). I.e the the time efficiency linearly depends on the number of elements in the linked list.

What are the advantages of linked lists over arrays?

In linked lists elements do not have to be moved after an element is inserted or deleted.. In arrays elements have to be moved after an element is inserted or deleted. Hence insert and delete operations are more efficient in linked lists compared to arrays.

The size of an array is fixed when it is initially created. This leads to inefficiencies since the array usually turns out to be too big or small. Linked lists uses exactly as much memory as needed, and can dynamically expand to use more memory as more elements are added to the linked list.