Stacks, queues, and doubly linked lists -data structures

 

Stacks, queues, linked lists, and doubly linked lists are all data structures that store data in a linear fashion. However, they each have different characteristics and are used for different purposes.

Stacks are a data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last item that is inserted into the stack is the first item that is removed. Stacks are often used to implement functions like undo and redo, as well as to evaluate mathematical expressions.

Queues are a data structure that follows the First-In-First-Out (FIFO) principle. This means that the first item that is inserted into the queue is the first item that is removed. Queues are often used to implement processes like printing jobs or tasks that need to be executed in order.

 

Linked lists are a data structure that stores data in a linked fashion. This means that each node in the list contains a pointer to the next node in the list. Linked lists can be either singly linked or doubly linked.

Singly linked lists can only be traversed in one direction, while doubly linked lists can be traversed in both directions. Linked lists are often used to implement lists, trees, and graphs.

Doubly linked lists are a type of linked list that has pointers to both the next node and the previous node in the list. This allows doubly linked lists to be traversed in both directions, which makes them more versatile than singly linked lists. Doubly linked lists are often used to implement stacks, queues, and linked lists.

Here is a table that summarizes the key differences between stacks, queues, linked lists, and doubly linked lists:

Feature	Stack	Queue	Linked list	Doubly linked list
Data structure	LIFO	FIFO	Linked	Linked
Direction of traversal	One direction only	One direction only	Both directions	Both directions
Memory usage	Less memory per node	Less memory per node	More memory per node	More memory per node
Applications	Undo/redo, mathematical expressions	Printing jobs, tasks	Lists, trees, graphs	Stacks, queues, linked lists

 

 

//code for a DoublyLinkedList class in Java

public class DoublyLinkedList {

 

    private Node head;

    private Node tail;

 

    public DoublyLinkedList() {

        head = null;

        tail = null;

    }

 

    public void addFirst(int data) {

        Node newNode = new Node(data);

        newNode.next = head;

        if (head != null) {

            head.prev = newNode;

        }

        head = newNode;

        if (tail == null) {

            tail = head;

        }

    }

 

    public void addLast(int data) {

        Node newNode = new Node(data);

        newNode.prev = tail;

        if (tail != null) {

            tail.next = newNode;

        }

        tail = newNode;

        if (head == null) {

            head = tail;

        }

    }

 

    public void removeFirst() {

        if (head == null) {

            return;

        }

        Node temp = head;

        head = head.next;

        if (head != null) {

            head.prev = null;

        } else {

            tail = null;

        }

        temp.next = null;

    }

 

    public void removeLast() {

        if (tail == null) {

            return;

        }

        Node temp = tail;

        tail = tail.prev;

        if (tail != null) {

            tail.next = null;

        } else {

            head = null;

        }

        temp.prev = null;

    }

 

    public void printList() {

        Node current = head;

        while (current != null) {

            System.out.print(current.data + " ");

            current = current.next;

        }

        System.out.println();

    }

private class Node {

        int data;

        Node next;

        Node prev;

 

        public Node(int data) {

            this.data = data;

            next = null;

            prev = null;

        }

    }

}