Как устроены списки в Java?

Question

[Username]

До этого работал со структурой только на си и я уяснил одно отличие, если разрываешь связь у элемента, то сборщик мусора за тобой приберёт.
Но вопросов куча, в чём отличие структуры от объекта? Добавление элемента работает так, что мы сначала создаём голову с нул значением ссылки, после добавления голова становится не нул, а ссылкой на добавленный объект?

Мне стало бы понятнее весь этот процесс, если бы вы смогли объяснить строчки в следующем коде:

public class List {
	
	
	public static class Node {
		public int data;
		public Node next;
	}

	
	private Node head;
	
	public  List() {
		head = null;		
	}
	

	
	@Override
	public String toString() {		
		String res = "<< ";		
		for (Node p = head; p != null; p = p.next) {
			res = res + p.data + " ";			
		}
		res = res + ">>";
		return res;
	}

	
	public  void addElementToHead(int value) {
		Node newNode = new Node();
		newNode.next = head;
		newNode.data = value;
		head = newNode;		
	}	
	
	
	
	
	public void deleteElement(Node delNode) {
		
		if (delNode == null) {
			return;
		}
		
		
		if (delNode == head) {
			head = head.next;
			return;
		} else {
			
			for (Node p = head; p != null; p = p.next) {
				if (p.next == delNode) {
					p.next = delNode.next;
				}		
			}			
		}		
		
	}
	
	
	
	
	public  void clear() {
		head = null;
	}
		

}

Answer 1

[Evhen]

Метод deleteElement реализован не правильно. Операция '==' сравнивает ссылки на объекты, а не сами объекты.

Например, если у вас в списке есть объект Node со значением поля data = 10, и вы хотите его удалить

Node delNode = new Node();
delNode.data = 10;

deleteElement(delNode); // ничего не удалится

потому что ссылка delNode и ссылка в списке ссылаются на разные объекты.
В джаве для сравнения переопределяют метод equals, в котором реализуют сравнение полей класса.

Вот так это должно выглядеть

if (delNode.equals(head)) {
      head = head.next;
      return;
    } else {
      
      for (Node p = head; p != null; p = p.next) {
        if (delNode.equals(p.next)) {
          p.next = delNode.next;
        }		
      }

Отличие структуры от класса в том, что класс позволяет реализовать наследование, инкапсуляцию и полиморфизм.

Comments

[Username]

public Node next; так мы создаём ссылку на объект, а он разве не будет ссылаться на самого себя?

[Evhen]

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

[Evhen]

Username: next - это ссылка на следующий в списке объект.

В данной реализации, новый элемент добавляется в голову списка.

head будет ссылаться на новый элемент, а в нем поле next будет ссылаться на бывший head

[pi314]

Eugene: Перекрытие метода equals() без одновременного перекрытия hashCode() - прямой путь в адъ, т.к. использование экземпляров таких классов в других, дже правильно написаных местах, чревато трудно отлавливаемыми косяками и иногда даже утечкой памяти.

А вообще, очень похоже, что странный код в вопросе получен неумелой доводкой напильником какого-то правильного кода из какого-то примера. Совершенно непонятно, зачем внутренний класс объявлен публичным и почему список добавляет int, а удаляет Node :)

[Evhen]

pi314: Согласен, лучше посмотреть исходники java.util.LinkedList.

Ну и стоит объяснять, зачем помимо equals переопределять и hashCode;)

[Username]

pi314: А можете привести пример правильного кода?

[pi314]

Username: Трудно понять, что значит "приавильного". Разных имплементаций связаного списка можно придумать вагон и маленькую тележку... имплементация может, например, гарантировать уникальность значений в списке, а может вообще не интересоваться значениями, может оперировать с элементами И значениями, а может только со значениями, или только с элементами, наконец, может быть generic. И для каждой разные подходы будут правильными.

Answer 2

[bromzh]

В яве несколько списков. Есть интерфейс List, есть несколько его реализаций. Самые популярные - это ArrayList (по-сути - динамический массив), есть LinkedList - связный список. Если ты немножко погуглишь, то найдёшь их исходники, они всё скажут сами за себя.
В будущем, чтобы реализовать свой список, лучше реализовывай стандартный интерфейс.