Today I wanted to study the lists in Java and such a question arose. Where are all the items listed? Those. for organizing a complete data structure, the values ​​must be stored in an array or something like this. And where are the values ​​stored in the lists?

  • 3
    Buy and read Robert Laforet’s book Data Structures and Java Algorithms. Very useful book. - Vlad from Moscow
  • Not very good advice, a book with huge listings of poorly written code. It is better to have a general book on algorithms and data structures, for example, Kormen, without reference to the language, although knowledgeable people say that it is not good either. - Artem Konovalov

2 answers 2

A linked list ( LinkedList ) is a dynamically changeable data structure that is built from a set of objects ( Nodes nodes) that refer to each other (see figure below). Each node usually stores one (to the next node) or two (to the next and previous nodes — such a list is called doubly linked) references to the neighbors and the list item value itself.

Thus, the value of the list is stored in classes of "wrappers" that are linked by links.

In the data structure itself, the LinkedList object stores only two links to the first and last (in a doubly linked list) list item, and access to any list item can be obtained by following the links of the nodes.

enter image description here

I recommend to look more in books devoted to algorithms and data structures, for example, you can start with the book "Algorithms in Java". Authors: Robert Sedgwick and Kevin Wayne.

    A newly created LinkedList object has two properties: header and size.

    header is a list pseudo-element. Its value is always null, a next and prev always indicate the first and last element of the list, respectively. Since the list is still empty at the moment, the next and prev properties point to themselves (that is, the header element). The size of the size list is 0.

    In other words, these are the same objects that just incidentally have links to the previous and next object.

    You can find out more in the article “ Data Structures in Pictures. LinkedList .

    • one
      It is not necessary for the list to have a field that counts the number of items in the list. And what's more, there is no need for the header to be a pseudo-element, as you write. You just mislead the author of the question. - Vlad from Moscow