Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Key Concepts

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Linked Lists

A linked list is a data structure that represents a sequence of nodes. In a singly linked list. each node points to the next node in the linked list. A doubly linked list gives each node pointers to both the next node and the previous node.

image

Unlike an array, a linked list does not provide constant time access to a particular “index” within the list. This means that if you’d like to find the Kth element in the list, you will need to iterate through K elements.

The benefit of a linked list is that you can add and remove items from the beginning of the list in constant time. For specific applications, this can be useful.

The node of a linked list would look something like this in code:

package LinkedLists;

import java.util.HashMap;

public class Node {
    Node next = null;
    int data;

    public Node (int n) {
        data = n;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

Could you think of a way to implement some methods like getNode(int n) and printAllNodes from a list? I’ll let you think about it for a second

imagen

Some basic functions 👀

These are some examples with fundamental functions that you could implement in your linked list. These for example could help you test future problems:

int length() {
    int counter = 1;
    Node n = this;
    while (n.next != null) {
        counter++;
        n = n.next;
    }
    return counter;
}

public String toString() {
    StringBuilder stringBuilder = new StringBuilder();
    Node n = this;
    while (n.next != null) {
        stringBuilder.append(n.data);
        stringBuilder.append(", ");
        n = n.next;
    }
    stringBuilder.append(n.data);
    stringBuilder.append(", ");
    return stringBuilder.toString();
}

public static Node getNode(Node head, int d) {
    Node n = head;

    while (n.next != null) {
        if (n.data != d) {
            n = n.next;
        } else {
            return n;
        }
    };

    if (n.data == d) return n;
    return null;
}

Implementing a double linked list 🎈

Now that you know all this you should be able to replicate it in a Double Linked List 😃, Try doing it yourself first, here is how I’ve implemented it:

public class DoubleLinkedListNode {
    int data;
    public DoubleLinkedListNode next = null;
    public DoubleLinkedListNode prev = null;

    public DoubleLinkedListNode(int n) {
        data = n;
    }

    void appendToTail(int d) {
        DoubleLinkedListNode newNode = new DoubleLinkedListNode(d);
        DoubleLinkedListNode n = this;

        while(n.next != null) {
            n = n.next;
        }
        n.next = newNode;
        newNode.prev = n;
    }
}

Example: Deleting a node from a linked list

Same thing here, how do you think a Linked List would get rid of a node, in this case in Java? We would have to link the previous node to the next Node (this.next = next.next) like this:

public static Node deleteNode(Node head, int d) {
    Node n = head;

    if(n.data == d) {
        return n.next;
    }

    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
            return head;
        }
        n = n.next;
    }
    return head;
}

The Runner technique 🏃‍♀️

The “runner” (or second pointer) technique is used in many linked list problems. The runner technique means that you iterate through the linked list with two pointers simultaneously, with one ahead of the other. The “fast” node might be ahead by a fixed amount, or it might be hopping multiple nodes for each one node that the “slow” node iterates through.

For example you could have one pointer p1(the fast pointer) move every two elements for everyone move that p2 makes. When p1 hits the end of the linked list, p2 will be at the midpoint. Then, move p1 back to the front and begin “weaving” the elements. On each iteration, p2 selects an element and inserts it after p1.

Note on recursion 📔

You should explore solving this type of problems in a recursive manner, as many times it could be easier to write. However, you remember that recursive algorithms will take at least O(N) space, and that all iterative algorithms can also be implemented recursively.

Last updated on 3/26/2020
← DIY OptimisationStack & Queues →
  • Some basic functions 👀
  • Implementing a double linked list 🎈
  • Example: Deleting a node from a linked list
  • The Runner technique 🏃‍♀️
  • Note on recursion 📔
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr