Algorithms and Data structures – Linked-list -Java implements one-way linked lists

Unidirectional linked lists in data structures

Niklaus Wirth, the Turing-prize winner and father of PASCAL, famously declared that “Algorithm+Data Structures=Programs” were almost universal in computing.

Data structure refers to the way a computer stores and organizes data. The logical structure of data is divided into linear structure and nonlinear structure.

A linear structure is a collection of ordered data elements, and the relationship between the data elements is one-to-one, that is, except for the first and last data elements, all the other data elements are end to end.

The two most basic ways to represent collections of elements are arrays and linked lists.

An array is an ordered sequence of elements. A one-dimensional array is a linear data structure. The advantage of an array is that you can access any element through an index and find it quickly. The disadvantage of arrays is that the number of elements in the array is known when the array is initialized, and inserting and deleting elements is very complicated.

Linked lists are a good way to overcome the disadvantages of arrays. The size of the space used is proportional to the number of elements, that is, there is no need to provide an initial size, and it is easier to insert and delete elements without “affecting everything”. The disadvantage of linked lists is that they require access to any element by reference, and lookup can be complex.

A linked list is a recursive data structure. The general linked list is divided into unidirectional linked list and bidirectional linked list two implementations.

Unidirectional linked list (single linked list, linear linked list) is a kind of linked list, which is characterized by the link direction of the list is unidirectional, access to the list by starting from the head, in order to read down. Bidirectionally linked lists (doubly linked lists) have two Pointers in each data node, one pointing to a direct successor and the other to a direct precursor. So, starting from any node in a bidirectional linked list, you can easily access its predecessors and successors.

The following uses the Java language to implement one-way linked lists to show the related operations of linked lists.

Java implements one-way linked lists

Only two attributes need to be defined for each node of a one-way linked list: the element of the current node and the next node.

class Node{
    Item item;
    Node node;
}
Copy the code

Use linked lists to implement stacks

Stack is a kind of first in last out (FILO) data structure. If you implement stack through array, you need to consider the problem of array expansion, which can be solved by linked list.

The following stack is implemented through a linked list and demonstrates the addition and division of nodes to the head of the list.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack;

public interface Stack<Item> {

    /**
     * add an item
     *
     * @param item
     */
    void push(Item item);

    /**
     * remove the most recently added item
     *
     * @return* /
    Item pop(a);

    /**
     * is the stack empty?
     *
     * @return* /
    boolean isEmpty(a);

    /** * number of items in the stac */
    int size(a);

}

Copy the code

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl;

import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack;

import java.util.Iterator;

/** * lists implement iterable stacks *@param <Item>
 * @author ijiangtao.net
 */
public class IterableLinkedListStack<Item> implements Stack<Item>,可迭代<Item> {
    /** Top of stack */
    private Node first;

    /** Number of stack elements */
    private int N;

    /** Defines the list node */ through the inner class
    private class Node{
        Item item;
        Node next;
    }

    /** * adds elements to the top of the stack, i.e. inserts nodes * at the head of the list@param item
     */
    @Override
    public void push(Item item) {

        Node oldFirst=first;

        first=new Node();
        first.item=item;
        first.next=oldFirst;

        N++;
    }

    /** * Removes an element from the top of the stack@return* /
    @Override
    public Item pop(a) {
        Item item=first.item;
        first=first.next;
        N--;
        return item;
    }

    @Override
    public boolean isEmpty(a) {
        return N==0;
    }

    @Override
    public int size(a) {
        return N;
    }


    @Override
    public Iterator<Item> iterator(a) {
        return new ListIterator();
    }

    /** * supports iterative methods to implement internal classes */
    private class ListIterator implements Iterator<Item> {

        private Node current = first;

        @Override
        public boolean hasNext(a) {
            / / or N! = 0
            returncurrent ! =null;
        }

        @Override
        public Item next(a) {
           Item item=current.item;
           current=current.next;
           return item;
        }

        @Override
        public void remove(a) {
            throw newUnsupportedOperationException(); }}public static void main(String[] args) {

        / / test
        Stack<String> stack=new IterableLinkedListStack<>();
        stack.push("aa");
        stack.push("bbb");
        stack.push("abc");

        for (String s:(IterableLinkedListStack<String>)stack) {
            System.out.println(s);
        }

        System.out.println("stack.size="+stack.size());
        System.out.println("stack.pop="+stack.pop());
        System.out.println("stack.size="+stack.size());
        System.out.println("stack.isEmpty="+stack.isEmpty());

        System.out.println("stack.pop="+stack.pop());
        System.out.println("stack.pop="+stack.pop());
        System.out.println("stack.size="+stack.size());
        System.out.println("stack.isEmpty="+stack.isEmpty());

        // Test the output
        /** * abc * bbb * aa * stack.size=3 * stack.pop=abc * stack.size=2 * stack.isEmpty=false * stack.pop=bbb * stack.pop=aa * stack.size=0 * stack.isEmpty=true */}}Copy the code

Queues are implemented using linked lists

Queue is a collection model based on first in first out (FIFO) policy.

The following implements queues based on linked lists and demonstrates their use.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.queue;

/** * queue *@author ijiangtao.net
 * @param <Item>
 */
public interface Queue<Item> {

    /** * whether the queue is empty *@return* /
    boolean isEmpty(a);

    /** * Queue size *@return* /
    int size(a);

    /** * join the team *@param item
     */
    public void enqueue(Item item);

    /** ** out of line *@return* /
    public Item dequeue(a);

}
Copy the code

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.queue.impl;

import net.ijiangtao.tech.algorithms.algorithmall.datastructure.queue.Queue;

import java.util.Iterator;

/** * queue *@author ijiangtao.net
 * @param <Item>
 */
public class IterableLinkedListQueue<Item> implements Queue<Item>,可迭代<Item>{

    /** queue head, the first node to join the queue */
    private Node first;

    /** The last node to join the queue */
    private Node last;

    /** The number of elements in the queue */
    private int N;

    private class Node{
        Item item;
        Node next;
    }

    @Override
    public boolean isEmpty(a) {
        / / or N = = 0
        return first==null;
    }

    @Override
    public int size(a) {
        return N;
    }

    /** * add an element * to the end of the queue@param item
     */
    @Override
    public void enqueue(Item item) {
        Node oldLast=last;

        last=new Node();
        last.item=item;
        last.next=null;

        if (isEmpty()){
            first=last;
        }else {
            oldLast.next=last;
        }

        N++;
    }

    /** * remove the queue head element *@return* /
    @Override
    public Item dequeue(a) {
        Item item=first.item;
        first=first.next;

        if (isEmpty()){
            last=null;
        }

        N--;

        return item;
    }

    @Override
    public Iterator<Item> iterator(a) {
        return new ListIterator();
    }

    /** * supports iterative methods to implement internal classes */
    private class ListIterator implements Iterator<Item> {

        private Node current = first;

        @Override
        public boolean hasNext(a) {
            / / or N! = 0
            returncurrent ! =null;
        }

        @Override
        public Item next(a) {
            Item item=current.item;
            current=current.next;
            return item;
        }

        @Override
        public void remove(a) {
            throw newUnsupportedOperationException(); }}public static void main(String[] args) {

        / / test
        Queue<String> queue=new IterableLinkedListQueue<>();
        queue.enqueue("aa");
        queue.enqueue("bbb");
        queue.enqueue("abc");

        for (String s:(IterableLinkedListQueue<String>)queue) {
            System.out.println(s);
        }

        System.out.println("queue.size="+queue.size());
        System.out.println("queue.dequeue="+queue.dequeue());
        System.out.println("queue.size="+queue.size());
        System.out.println("queue.isEmpty="+queue.isEmpty());

        System.out.println("queue.dequeue="+queue.dequeue());
        System.out.println("queue.dequeue="+queue.dequeue());
        System.out.println("queue.size="+queue.size());
        System.out.println("queue.isEmpty="+queue.isEmpty());

        // Test the output
        /** * aa * bbb * abc * queue.size=3 * queue.dequeue=aa * queue.size=2 * queue.isEmpty=false * queue.dequeue=bbb * queue.dequeue=abc * queue.size=0 * queue.isEmpty=true */}}Copy the code

Implement knapsacks using linked lists

A knapsack is a container that can only be added but not removed. Its function is to collect elements and iterate over the collected elements.

Packages, like stacks, follow a first-in, last-out policy (FILO).

A linked list-based knapsack implementation is provided below.

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.bag;

/** * backpack *@author ijiangtao.net
 * @param <Item>
 */
public interface Bag<Item> extends 可迭代<Item>{

    /** * Add elements to the backpack *@param item
     */
    void add(Item item);

}
Copy the code

package net.ijiangtao.tech.algorithms.algorithmall.datastructure.bag.impl;

import net.ijiangtao.tech.algorithms.algorithmall.datastructure.bag.Bag;

import java.util.Iterator;

public class IterableLinkedListBag<Item> implements Bag<Item> {

    private Node first;

    private class Node{
        Item item;
        Node next;
    }

    @Override
    public void add(Item item) {
        Node oldFirst=first;

        first=new Node();
        first.item=item;
        first.next=oldFirst;

    }

    @Override
    public Iterator<Item> iterator(a) {
        return new ListIterator();
    }

    /** * supports iterative methods to implement internal classes */
    private class ListIterator implements Iterator<Item> {

        private Node current = first;

        @Override
        public boolean hasNext(a) {
            / / or N! = 0
            returncurrent ! =null;
        }

        @Override
        public Item next(a) {
            Item item=current.item;
            current=current.next;
            return item;
        }

        @Override
        public void remove(a) {
            throw newUnsupportedOperationException(); }}public static void main(String[] args) {

        / / test
        Bag<String> bag=new IterableLinkedListBag<>();
        bag.add("aa");
        bag.add("bbb");
        bag.add("abc");

        for (String s:bag) {
            System.out.println(s);
        }

        // Test the output
        /** * abc * bbb * aa */}}Copy the code