Key differences between Array List and Linked List

Array List

ArrayList in Java is a resizable array implementation of the List interface. Unlike standard arrays which have a fixed size, ArrayLists can dynamically resize as elements are added or removed. They provide a convenient way to store elements that can be accessed via indices, similar to arrays. Internally, ArrayList uses an array to store the elements, and when the array fills, it creates a new, larger array and copies the old elements to the new array. This makes adding elements (especially appending at the end) relatively efficient. However, resizing the array and inserting or removing elements from the middle of the list can be slower. ArrayList is part of the Java Collections Framework, providing methods for easy manipulation of stored elements.

Functions of Array List:

• Add Elements:

You can add elements to an ArrayList using the add(E e) method, which appends the element at the end of the list, or add(int index, E element) to insert an element at a specific position.

• Remove Elements:

Elements can be removed by specifying either the index (remove(int index)) or the element itself (remove(Object o)), if it exists in the list.

• Access Elements:

Use the get(int index) method to access an element at a specific index.

• Modify Elements:

set(int index, E element) method allows replacing the element at the specified index with a new element.

• Size of the List:

size() method returns the number of elements in the list.

• Check if Empty:

isEmpty() method checks whether the list contains any elements.

• Clear the List:

clear() removes all elements from the list, effectively resetting it.

• Search:

Includes contains(Object o) to check if a specific element is in the list, and indexOf(Object o) and lastIndexOf(Object o) to find the first or last occurrence of an element, respectively.

• Iterate Over Elements:

Provides iterators (iterator() and listIterator()) to sequentially access elements in the list. You can also use enhanced for-loops directly.

• Convert to Array:

toArray() method converts the list into a plain array.

• Sort:

Using Collections.sort() or passing a Comparator to sort the list based on custom ordering.

• Sublist:

subList(int fromIndex, int toIndex) method returns a view of a portion of the list between the specified fromIndex, inclusive, and toIndex, exclusive.

Example of Array List:

This example demonstrates some common operations such as adding, removing, and accessing elements.

import java.util.ArrayList;

public class ArrayListExample {

    public static void main(String[] args) {

        // Creating an ArrayList of String type

        ArrayList<String> names = new ArrayList<>();

        // Adding elements to the ArrayList

        names.add(“Alice”);

        names.add(“Bob”);

        names.add(“Charlie”);

        names.add(“Diana”);

        // Displaying the ArrayList

        System.out.println(“Initial list: ” + names);

        // Accessing elements from the ArrayList

        System.out.println(“Element at index 1: ” + names.get(1));

        // Adding an element at a specific position

        names.add(2, “Eve”);

        // Removing an element from the ArrayList

        names.remove(“Alice”); // Removes “Alice”

        names.remove(2); // Removes the element at index 2 (which is now “Charlie” after the previous removal)

        // Displaying the final list after additions and deletions

        System.out.println(“Modified list: ” + names);

        // Using size() to print the number of elements in the ArrayList

        System.out.println(“Current size of list: ” + names.size());

        // Checking if the list contains “Diana”

        if (names.contains(“Diana”)) {

            System.out.println(“Diana is in the list.”);

        }

        // Displaying each element using enhanced for-loop

        System.out.println(“Elements in the list:”);

        for (String name : names) {

            System.out.println(name);

        }

    }

}

In this example:

• ArrayList called names is created to store strings.
• Elements are added to names using the add
• The remove method is used to remove elements both by object content and by index.
• get method is used to access an element.
• Program checks for the existence of an element using contains.
• The list and its size are printed before and after modifications, demonstrating how dynamic arrays like ArrayList handle changes in their content.

Linked List

LinkedList in Java is a fundamental data structure that implements the List and Deque interfaces from the Java Collections Framework. Unlike arrays or ArrayLists, which use contiguous memory locations, LinkedList consists of elements where each element, known as a node, contains both the data and a reference to the next and possibly the previous node in the sequence. This allows for efficient insertion and removal of elements at any position in the list, especially at the beginning and end, as no shifting of elements is required. LinkedList is ideal for scenarios where frequent addition and deletion operations are needed but is less efficient for random access of elements.

Functions of Linked List:

• add(E e):

Adds an element to the end of the list.

• add(int index, E element):

Inserts the specified element at the specified position in the list.

• addFirst(E e) and addLast(E e):

Adds an element to the beginning or the end of the list, respectively.

• remove():

Removes and returns the first element of the list.

• remove(int index):

Removes the element at the specified position in the list.

• remove(Object o):

Removes the first occurrence of the specified element from the list, if it is present.

• get(int index):

Returns the element at the specified position in the list.

• getFirst() and getLast():

Returns the first or last element of the list, respectively.

• set(int index, E element):

Replaces the element at the specified position with the specified element.

• size():

Returns the number of elements in the list.

• clear():

Removes all of the elements from the list.

• contains(Object o):

Returns true if the list contains the specified element.

• indexOf(Object o) and lastIndexOf(Object o):

Returns the index of the first or last occurrence of the specified element in this list, or -1 if this list does not contain the element.

• iterator() and listIterator():

Returns an iterator over the elements in the list in proper sequence. The listIterator also allows bidirectional traversal of the list.

• toArray():

Returns an array containing all of the elements in the list in proper sequence.

Example of Linked List:

This example includes creating a LinkedList, adding items, removing items, and accessing items:

import java.util.LinkedList;

public class LinkedListExample {

    public static void main(String[] args) {

        // Creating a LinkedList

        LinkedList<String> names = new LinkedList<>();

        // Adding elements to the LinkedList

        names.add(“Alice”);

        names.add(“Bob”);

        names.addLast(“Charlie”);

        names.addFirst(“Dana”);

        // Print all elements in the LinkedList

        System.out.println(“Initial LinkedList: ” + names);

        // Removing elements from the LinkedList

        names.remove(“Bob”);  // Remove by value

        names.removeFirst();  // Remove the first element

        names.removeLast();   // Remove the last element

        // Print after removals

        System.out.println(“LinkedList after removals: ” + names);

        // Adding elements at a specific position

        names.add(0, “Eve”);

        names.add(1, “Zack”);

        // Print after adding more elements

        System.out.println(“LinkedList after adding more elements: ” + names);

        // Accessing elements

        String firstItem = names.getFirst();

        String lastItem = names.getLast();

        System.out.println(“First Item: ” + firstItem + “, Last Item: ” + lastItem);

        // Using enhanced for loop to print all elements

        System.out.print(“Complete LinkedList: “);

        for (String name : names) {

            System.out.print(name + ” “);

        }

    }

}

Output:

Initial LinkedList: [Dana, Alice, Bob, Charlie]

LinkedList after removals: [Alice]

LinkedList after adding more elements: [Eve, Zack, Alice]

First Item: Eve, Last Item: Alice

Complete LinkedList: Eve Zack Alice

This example covers key functionalities such as adding elements to both ends of the list, removing elements, and accessing elements. LinkedList is particularly useful when you need to manipulate data frequently, such as adding or removing elements from the beginnings or ends of lists.

Key differences between Array List and Linked List

Key Similarities between Array List and Linked List

• Linear Data Structures:

Both arrays and linked lists are linear data structures, meaning they store elements in a sequential manner.

• Sequential Access:

In both arrays and linked lists, elements can be accessed sequentially. To reach a particular element, you start at the beginning and follow the sequence until you find the desired element.

• Store Homogeneous Data:

Typically, both arrays and linked lists are used to store homogeneous data types, though in some languages like Python, this is more flexible.

• Basic Operations:

Both support basic operations such as insertion, deletion, and traversal, though the efficiency and implementation of these operations differ.

• Usage in Building Other Structures:

Both can be used as the underlying data structure to build more complex data structures like stacks and queues.

• Iterable:

In many programming environments, both arrays and linked lists can be iterated over using loops, making them compatible with iterative algorithms.

• Support for Generic Types:

In languages that support generics, such as Java and C#, both arrays and linked lists can hold generic types allowing them to be more flexible and type-safe.

• Implementation of Interfaces:

In languages like Java, both arrays and linked lists can implement interfaces, such as the Iterable interface, enabling consistent interaction patterns.