DEV Community

loading...
Cover image for LinkedList in Java

LinkedList in Java

Britt Codes
Java, Spring, Ruby, Ruby on Rails, TypeScript, JavaScript, React, Redux, Angular
Updated on ・4 min read

What Is A Data Structure?

A data structure is a way to store, organized/manage, and retrieve data effectively. Data structures are used in almost every program and are very important to learn and understand in software engineering.

What Is A LinkedList?

A LinkedList is a linear (O(n)) data structure that represents a sequence of elements that are the same type, which are often called Nodes. In each Node, there is the data and a pointer(s) that points to the adjacent and/or previous Node. The first Node of the list is referred to as the head, and the last Node's pointer in the list points to null or the head (Circular LinkedList). This data structure is dynamic, which means it can grow and shrink based on the number of elements inserted and deleted from the LinkedList.

In order to traverse a LinkedList, you have to start at the beginning (head) and go through each one until you've reached the desired Node. LinkedList does not allow random access.

In Java, the LinkedList implements the following interfaces, Serializable, Cloneable, Iterable, Collection, Deque, List, Queue. This is important because it gives the LinkedList data structure flexibility in its operations and usage within a program.

Below I'll demonstrate how to build a LinkedList (Singly) and some of the operations. However, the implementation will not be as specific as the implementation in the documentation, click here for the documentation.

Implementation

Singly LinkedList

SinglyLinkedList

The Singly LinkedList has only one pointer for each Node that points to the memory address of the next Node. (See below)

/**
 * @author brittcodes
 *
 */
public class SinglyLinkedList {

    Node head;

    static class Node {

        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            next = null;
        }

        public String toString() {
            return "Node [ data=" + data + ", next=" + next + " ]";
        }

    }






    /**
     * Inserts Node at the end of the list
     * 
     * @param data, primitive data type int
     */
    public void add(int data) {
        //create a new node, put data in it
        Node newNode = new Node(data);



        //if head is null, set new node as head
        if(head == null) {
            head = newNode;
            return;
        }

        //set new node next to null
        newNode.next = null;

        //find the node with next as null, and set that node to the new node
        Node last = head;
        while(last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }







    /**
     * Inserts a new Node after a given previous Node
     * 
     * 
     * @param data, primitive data type int
     */
    public void insertAfter(Node node, int data) {
        //create a new node, put data in it
        Node newNode = new Node(data);

        //set newNode's next to node's next
        newNode.next = node.next;

        //set node's next to new Node
        node.next = newNode;

                //if list is empty, set newNode to head
        if(head == null) {
            newNode = head;
        }
    }







    /**
     * Inserts a new Node at beginning of list
     * 
     * 
     * @param data, primitive data type int
     */
    public void insertToFront(int data) {

        // create a node, put data in it
        Node newNode = new Node(data);

        // set new node's pointer to the head
        newNode.next = head;

        // if list is empty, set newNode to head
        if (head == null) {
            newNode = head;
        }

        // make newNode the head
        head = newNode;

    }






    /**
     * Prints out the LinkedList
     * 
     */
    public void printList() {
        // traverse the nodes and print

        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
        System.out.println();
    }






    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        list.head.next = second;
        second.next = third;
        list.insertToFront(6);
        list.printList();
        list.insertAfter(third, 8);
        list.printList();
        list.add(23);
        list.printList();
    }

}
Enter fullscreen mode Exit fullscreen mode

Doubly LinkedList

DoublyLinkedList

The Doubly LinkedList has two pointers for each Node. One pointer pointing to the memory address of the previous Node, and the other pointer pointing to the memory address of the next/adjacent Node.

/**
 * @author brittcodes
 *
 */
public class DoublyLinkedList {

    Node head;

    static class Node {
        int data;
        Node next;
        Node previous;

        public Node(int data) {
            this.data = data;
            next = null;
            previous = null;
        }

        public String toString() {
            return "Node [ data=" + data + ", next=" + next + " ]";
        }
    }








    /**
     * Prints list forwards and backwards
     * 
     * @param n, represents Node
     */
    public void printList(Node n) {

        Node last = null;

        // Prints forward
        System.out.println("\nTraverse forward");
        while (n != null) {
            System.out.print(n.data + " ");
            last = n;
            n = n.next;
        }

        // Prints backwards
        System.out.println("\nTraverse backward");
        while (last != null) {
            System.out.print(last.data + " ");
            last = last.previous;
        }

    }









    /**
     * Inserts Node to the beginning of list
     * 
     * @param data, primitive data type int
     */
    public void insertToFront(int data) {

        // create a new Node
        // put in the data
        Node newNode = new Node(data);

        // Make next of new node as head and previous as NULL
        newNode.next = head;
        newNode.previous = null;

        // change previous of head node to new node
        if (head != null) {
            head.previous = newNode;
        }

        // move the head to point to the new node
        head = newNode;

    }







    /**
     * Inserts element after specified prevNode with data at the end of the list
     * 
     * @param prevNode
     * @param data
     */
    public void insertAfter(Node prevNode, int data) {

        if (prevNode == null) {
            System.out.println("The given previous node cannot be NULL ");
            return;
        }

        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;

        newNode.previous = prevNode;

        if (newNode.next != null) {
            newNode.next.previous = newNode;
        }

    }

    public void insertBefore(Node node, int data) {

        Node newNode = new Node(data);

        if ((head == null) && (node == null)) {
            head = newNode;
        }

        newNode.previous = node.previous;

        node.previous = newNode;

        newNode.next = node;

        if (newNode.previous != null) {
            newNode.previous.next = newNode;
        }
    }









    /**
     * Inserts element at the end of the list
     * 
     * @param data
     */
    public void insertAtEnd(int data) {

        // create a new Node
        // put in the data
        // make new Node next point to null
        // traverse list until at last node
        // make new Node previous point to last Node
        // make last node next point to new Node

        Node newNode = new Node(data);
        Node last = head;
        newNode.next = null;

        if (head == null) {
            head = newNode;
            newNode.previous = null;
            return;
        }

        while (last.next != null) {
            last = last.next;
        }

        newNode.previous = last;
        last.next = newNode;

    }









    public static void main(String[] args) {
        DoublyLinkedList doubly = new DoublyLinkedList();

        doubly.head = new Node(4);
        Node second = new Node(5);
        Node third = new Node(6);

        doubly.head.next = second;
        second.next = third;

        third.previous = second;
        second.previous = doubly.head;

        doubly.printList(doubly.head);
        doubly.insertAfter(doubly.head, 10);
        doubly.printList(doubly.head);
        doubly.insertAtEnd(25);
        doubly.printList(doubly.head);
        doubly.insertBefore(second, 101);
        doubly.printList(doubly.head);

    }

}


Enter fullscreen mode Exit fullscreen mode

Discussion (2)

Collapse
ben profile image
Ben Halpern

Test

Collapse
brittcodes profile image
Britt Codes Author

LOL