Data Structures: Linked Lists

In order to get ready for a technical interview, I’ll post some of the topics related to my blog. The content that I got is all from HackerRank’s Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell YouTube Video which is linked. Their videos are extremely helpful and everything I posted down below is my notes on it.


Linked Lists: A sequence of elements where each element links to the next element to the next element …

  • Can contain Strings, Numbers, Characters, etc.
  • Elements can be sorted or unsorted
  • Can contain duplicated elements or unique

Screen Shot 2018-02-05 at 10.51.24 AM

Difference between Array and LinkedList
In an array, elements are indexed. a[3] instantly goes to the 4th element.

Disadvantage of LinkedLists

  • Slow [O(n) Linear] to get to the kth element

Advantage of LinkedLists

  • Insertion [O(1) prepend, O(n) append] and deletion can be quick

DOUBLY LINKED LISTS
Has reference to the previous elements

Screen Shot 2018-02-05 at 10.55.27 AM

Implementation of Linked Lists:

class Node {

    Node next;

    int data;


    public Node(int data) {

        this.data = data;

    }


}


public class LinkedLists {


    Node head;


    public void append(int data) {

        if (head == null) {

            head = new Node(data);

            return;

        }

        Node current = head;

        while (current.next != null) {

            current = current.next;

        }

        current.next = new Node(data);

    }


    public void prepend(int data) {

        Node newHead = new Node(data);

        newHead.next = head;

        head = newHead;

    }


    public void deleteWithValue(int data) {

        if (head == null)

            return;


        if (head.data == data) {

            head = head.next;

            return;

        }


        Node current = head;

        while (current.next != null) {

            if (current.next.data == data) {

                current.next = current.next.next;

                return;

            }

            current = current.next;

        }

    }

}


Code Formatted by ToGoTutor

 

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s