Записки программиста Программирование и не только

[Java] Структуры данных. Список

Список, для начала, возьмем простой линейный односвязный.

Список есть динамическая структура данных.

Каждый элемент списка содержит в себе данные и указатель на следующий элемент.
Возьмем простой вариант данных в списке - просто целые числа.
Элемент списка:

class ListElement {
    ListElement next;    // указатель на следующий элемент
    int data;            // данные
}

Сам список также будет классом.
Будет содержать в себе указатель на первый элемент списка и на последний - head и tail.
Также реализуем методы:
1. Добавление элемента в конец списка
2. Добавление элемента в начало списка
3. Удаление элемента по значению
4. Печать всего списка

class List {
    private ListElement head;       // указатель на первый элемент
    private ListElement tail;       // указатель последний элемент

    void addFront(int data)           //добавить спереди
    {
        ListElement a = new ListElement();  //создаём новый элемент
        a.data = data;              //инициализируем данные. 
                                    // указатель на следующий элемент автоматически инициализируется как null
        if(head == null)            //если список пуст
        {                           //то указываем ссылки начала и конца на новый элемент
            head = a;               //т.е. список теперь состоит из одного элемента
            tail = a;
        }
        else {
            a.next = head;          //иначе новый элемент теперь ссылается на "бывший" первый
            head = a;               //а указатель на первый элемент теперь ссылается на новый элемент 
        }
    }

    void addBack(int data) {          //добавление в конец списка
        ListElement a = new ListElement();  //создаём новый элемент
        a.data = data;
        if (tail == null)           //если список пуст
        {                           //то указываем ссылки начала и конца на новый элемент
            head = a;               //т.е. список теперь состоит из одного элемента
            tail = a;
        } else {
            tail.next = a;          //иначе "старый" последний элемент теперь ссылается на новый
            tail = a;               //а в указатель на последний элемент записываем адрес нового элемента
        }
    }

    void printList()                //печать списка
    {
        ListElement t = head;       //получаем ссылку на первый элемент   
        while (t != null)           //пока элемент существуе
        {
            System.out.print(t.data + " "); //печатаем его данные
            t = t.next;                     //и переключаемся на следующий
        }
    }

    void delEl(int data)          //удаление элемента
    {
        if(head == null)        //если список пуст - 
            return;             //ничего не делаем

        if (head == tail) {     //если список состоит из одного элемента
            head = null;        //очищаем указатели начала и конца
            tail = null;
            return;             //и выходим
        }

        if (head.data == data) {    //если первый элемент - тот, что нам нужен
            head = head.next;       //переключаем указатель начала на второй элемент
            return;                 //и выходим
        }

        ListElement t = head;       //иначе начинаем искать
        while (t.next != null) {    //пока следующий элемент существует
            if (t.next.data == data) {  //проверяем следующий элемент
                if(tail == t.next)      //если он последний
                {
                    tail = t;           //то переключаем указатель на последний элемент на текущий
                }
                t.next = t.next.next;   //найденный элемент выкидываем
                return;                 //и выходим
            }
            t = t.next;                //иначе ищем дальше
        }
    }
}

Тонкости Java-реализации:
Освобождать память не надо - достаточно чтобы на выделенные по new участок не было указателей и тогда сборщик мусора сам её почистит.
Все переменные являются ссылками на объекты, так что нет заморочек с разыменование указателей и передачи адресов.

Испоьзование:

public class Main {
    public static void main(String[] args) {
        List ml = new List();
        ml.addBack(1);
        ml.addBack(2);
        ml.addBack(3);
        ml.addFront(6);

        ml.printList();
        System.out.println();

        ml.delEl(6);
        ml.delEl(5);
        ml.delEl(12);
        ml.delEl(2);

        ml.printList();
        System.out.println();
    }
}

Распечатает:

6 1 2 3 
1 3 

А теперь немного магии :)
С целочисленным списком скучно. Сделаем элемент списка универсальным!
Это можно сделать при помощи "шаблонизации"
Причем какой именно тип - будет автоматически определяться при сборке!

class ListElement<E> {
    ListElement next;
    E data;
}

class List<E> {
    private ListElement head;       // указатель на первый элемент
    private ListElement tail;       // указатель последний элемент

    void addFront(E data)           //добавить спереди
    {
        ListElement a = new ListElement();  //создаём новый элемент
        a.data = data;              //инициализируем данные. 
                                    // указатель на следующий элемент автоматически инициализируется как null
        if(head == null)            //если список пуст
        {                           //то указываем ссылки начала и конца на новый элемент
            head = a;               //т.е. список теперь состоит из одного элемента
            tail = a;
        }
        else {
            a.next = head;          //иначе новый элемент теперь ссылается на "бывший" первый
            head = a;               //а указатель на первый элемент теперь ссылается на новый элемент 
        }
    }

    void addBack(E data) {          //добавление в конец списка
        ListElement a = new ListElement();  //создаём новый элемент
        a.data = data;
        if (tail == null)           //если список пуст
        {                           //то указываем ссылки начала и конца на новый элемент
            head = a;               //т.е. список теперь состоит из одного элемента
            tail = a;
        } else {
            tail.next = a;          //иначе "старый" последний элемент теперь ссылается на новый
            tail = a;               //а в указатель на последний элемент записываем адрес нового элемента
        }
    }

    void printList()                //печать списка
    {
        ListElement t = head;       //получаем ссылку на первый элемент   
        while (t != null)           //пока элемент существуе
        {
            System.out.print(t.data + " "); //печатаем его данные
            t = t.next;                     //и переключаемся на следующий
        }
    }

    void delEl(E data)          //удаление элемента
    {
        if(head == null)        //если список пуст - 
            return;             //ничего не делаем

        if (head == tail) {     //если список состоит из одного элемента
            head = null;        //очищаем указатели начала и конца
            tail = null;
            return;             //и выходим
        }

        if (head.data == data) {    //если первый элемент - тот, что нам нужен
            head = head.next;       //переключаем указатель начала на второй элемент
            return;                 //и выходим
        }

        ListElement t = head;       //иначе начинаем искать
        while (t.next != null) {    //пока следующий элемент существует
            if (t.next.data == data) {  //проверяем следующий элемент
                if(tail == t.next)      //если он последний
                {
                    tail = t;           //то переключаем указатель на последний элемент на текущий
                }
                t.next = t.next.next;   //найденный элемент выкидываем
                return;                 //и выходим
            }
            t = t.next;                //иначе ищем дальше
        }
    }
}

Изменения минимальны.
Вместо int пишем E. И к имени класса добавляем

<E>

Зато теперь можно сделать вот так:

public class Main {
    public static void main(String[] args) {
        List ml = new List();
        ml.addBack(1.0);
        ml.addBack(2);
        ml.addBack("brrr");
        ml.addFront(6);

        ml.printList();
        System.out.println();
    }
}

В выводе будет:

6 1.0 2 brrr