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

23Окт/1214

[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 
Комментарии (14) Пинги (0)
  1. Мне кажется, что в методе delEl(E data) ошибка. Если список состоит из одного элемента это еще не причина удалять его, надо еще проверить существует ли такой элемент: if (head == tail && head.data == data).

    • Задумка заключается в том, что head и tail это не элементы, а ссылки на элементы. И если они ссылаются друг на друга или на NULL, то список пуст.
      Данный пример является переводом примера с С++, где всё это нагляднее. Возможно на Java можно написать более красиво.

  2. Привет, можешь реализовать дополнительно indexOf, get(index)?

  3. А как удалять и добавлять элементы по индексу ?

  4. Вот вроде начал изучать Java. Потом отдельно начал изучать структуры данных. Такой реализации серьезно не ожидал. Четкая. Но разве это не жирно на каждый получается элемент списка предоставлять целый новый экземпляр класса в памяти?

  5. Спасибо за публикацию, очень правильно все написано!

  6. можете скинуть весь код ? буду очегь благодарен. я новичок хочу понять эту тему.


Отменить ответ

Нет обратных ссылок на эту запись.