Linked Lists

A linked list is a data structure used in computer science that consists of a sequence of nodes. Each node contains an element and a reference to the next node in the sequence. Linked lists are a dynamic data structure, which means that they can grow or shrink in size during program execution.

Linked lists are useful in situations where a programmer needs to insert or delete elements from a list frequently. Linked lists are often used in implementing data structures such as stacks, queues, and hash tables.

How Linked Lists Work

In a singly linked list, each node has a reference to the next node in the list. The first node in the list is called the head, and the last node in the list has a reference to null. To traverse the list, a programmer starts at the head and follows the next reference in each node until reaching the end of the list.

In a doubly linked list, each node has a reference to the next node and the previous node in the list. The first node in the list is called the head, and the last node in the list is called the tail. To traverse the list, a programmer can start at either end and follow the next and previous references in each node until reaching the other end of the list.

How to Implement a Linked List in Java

Here is an example of how to implement a singly linked list in Java.

Main


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
            
// This package is employed to run code on Codefinity.
package com.example;
// It is not required to be written in typical IDEs.

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


public class LinkedList {
    Node head;
   
    public LinkedList() {
        this.head = null;
    }
   
    public void add(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
   
    public void print() {
        Node current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
    }
}


public class Main {
    public static void main(String[] args) {
        LinkedList myList = new LinkedList();
        myList.add(5);
        myList.add(10);
        myList.add(15);
        myList.print();
    }
}

In this example, the Node class represents a node in the linked list, and the LinkedList class represents the linked list itself. The add() method adds a new node to the end of the list, and the print() method prints out the values of all nodes in the list.

Advantages of Linked Lists	Disadvantages of Linked Lists
Dynamic size: Linked lists can grow or shrink in size during program execution.	Slow access to the middle: Unlike arrays or `ArrayLists`, linked lists do not allow for direct access to elements in the middle of the list. Instead, a programmer must traverse the list to find the desired element.
Efficient insertion and deletion: Adding or removing an element from a linked list is O(1) time complexity, whereas adding or removing an element from an array or `ArrayList` is O(n) time complexity in the worst case.	Additional memory usage: Linked lists require additional memory to store the references to the next or previous node in the list.
No need to move elements: Adding or removing an element from a linked list does not require moving other elements, as it does with arrays or `ArrayLists`.	No random access: Linked lists do not support random access to elements.

1. Which of the following data structures is used to implement linked lists in Java?

2. Which of the following is true about doubly linked lists in Java?

Everything was clear?

Thanks for your feedback!

Section 1. Chapter 3