LinkedList

LinkedList is a linear data structure and in which elements are not stored in continuous location.

Singly-linked-list.svg

Image source Wikipedia

In simple Linkedlist each elements will contain 2 memory locations one is for data element and other is for address of next element.

Advantages of Linkedlist over arrays :

  1. Arrays are fixed in size and we have to specify the max memory when we declare an array whereas Linkedlist is dynamic.
  2. In Arrays insertion and deletions are takes more time. Because if we add element in array in the first or middle all other elements need to move and same in deletion also whereas in linkedlist it takes less time because when insert element in the middle address of element will be added to previous element and next element address will be added to current element.

Image result for linked list

Deleting an element.

Related image

Adding an element

Disadvantages:

  1. As each node required 2 memory location, it needs more memory.
  2. In linkedlist random access is not possible. So retrieving/accessing an element needs traversal of list from first until the element found.

Time Complexity:

Accessing an element : O(1) if the element in the first location.

O(n) if the element in the last location.

Insertion and deletion: O(1).

Simple LinkedList program with Java:

package com.gudla.linkedlist;

/**
 * Created by santhosh on 19/3/17.
 */
public class LinkedList {
    static Node head;

    static class Node{
        String data;
        Node next;
        Node(String string){
            data = string;
            next = null;
        }
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.head = new Node("Santhosh");
        Node first = new Node("Muni");
        Node second = new Node("Basha");

//        Assign address of first node to head and second node to first
        head.next = first;
        first.next = second;

        printData();
    }

    static void printData(){
        while (head != null){
            System.out.println(head.data);
            head = head.next;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s