How do linear data structures work

Linear data structures

Linear data structures

If data structures are used, it is usually a matter of managing any number of objects in a suitable data structure, e.g. all students in a school. In such a case it makes no sense to model all properties of a student as primitive data types and to create a separate field or similar for each property. Therefore, at the beginning of this chapter we first explain how objects can be used as data record stores. Then the linear data structures field, list, stack and queue are dealt with.

Objects vs. primitive data types

Objects as data storage

In this section we would like to model a student administration. We are designing a separate class for this Student and first model the required properties as attributes. If necessary, there are also methods for changing and querying the attributes.

In this example, the two attributes age and name have been defined. Both must be transferred to the when creating a student object (cf. constructor), both can also be changed afterwards using the set methods and queried at any time using the get methods.

publicclassSchueler {privateStringname; privateintalter; publicSchueler (Stringname, intalter) {this.name = name; this.alter = age;} publicvoidsetName (Stringname) {this.name = name;} publicStringgetName () {returnname;} publicvoidsetAlter (intalter) { this.alter = age;} publicintgetAlter () {returnalter;}}

Objects of a class that, as in this example, only function as data storage and have no or almost no program logic of their own, are called in Java Beans ("Coffee Beans").

Wrapper classes

The only data structure in Java that can manage primitive data types in addition to objects is the field. All other data structures (e.g. list, stack, queue, etc.) only allow objects to be saved.

But what should be done if it is sufficient for an application to only store numbers (e.g. ISBN numbers or shoe sizes)? Do you then have to laboriously design your own class as described in the student example?

For these rare cases there are so-called in Java Wrapper classes built-in.

primitive data typeWrapper classService method
intIntegerintValue ()
doubleDoubledoubleValue ()
charCharactercharValue ()
booleanBooleanboolValue ()

Example: A primitive int value 17 is "boxed" in an object of the Integer class.

inti = 17; Integeriobj = newInteger (i); // Boxing

In order to then read it out of the object again (unboxing), a corresponding service method is available for each wrapper class (see table).

intj = iobj.intValue (); // unboxing

field

The obvious data structure for managing objects is the field. It's built in to Java and is pretty easy to use.

Use of a field

At this point the example of a student administration should be taken up again. A corresponding class of pupils has already been developed in the previous section (see Objects as data storage).

The creation and use of a field via student objects is analogous to the use of a field via primitive data types (see also section Fields).

As can be seen in the source text, the student objects are first created and then placed in the appropriate positions as usual in a field. The method is available() shows an example of the passage through a field.

publicclassSchuelerverwaltung {privateSchueler [] meineschueler; publicSchuelerverwaltung () {Schuelers1 = newSchueler ("Otto", 14); Schuelers2 = newSchueler ("Susi", 13); Schuelers3 = newSchueler ("Hans", 15); meineschueler = newSchueler [3] ; meineschueler [0] = s1; meineschueler [1] = s2; meineschueler [2] = s3;} publicbooleanistVorhanden (string search name) {for (inti = 0; i

discussion

Advantages:

  • The field is built into Java and can be used without additional effort.
  • Access is possible to every field position. This enables a fast binary search with logarithmic effort to be implemented again.

Disadvantage:

  • The field is static, i.e. its size must be determined when it is created. As a result, it could either be much too large (wasted memory) or much too small (no subsequent insertion possible).

The disadvantage of static size is countered by dynamic data structures such as the list (see section List). The search tree represents the ideal combination of fast search and dynamics (see section Search tree).

list

The list is a linear data structure that is traversed sequentially (i.e. from front to back). Each element of the list only has access to its successor, which results in a linked structure.

The list is dynamic because new elements can be added to the chain at any position. A search on a list has a linear duration, since only a complete run from front to back is possible.

The high school class Cunning is generic, i.e. the class of the objects that are to be managed in the list is already determined when they are created. It is of course possible (even if only rarely makes sense) to also manage objects from subclasses of this class.

Build a list

In the following example, when the list is generated, it is specified that objects of the class String should be managed. With the help of the method append the strings are appended to the end of the list, which changes the order Babsi - Franzi - Susi results.

Strings1 = "Babsi"; Strings2 = "Franzi"; Strings3 = "Susi"; List l = newList (); l.append (s1); l.append (s2); l.append (s3 );

Go through a list

When going through a list (e.g. to carry out a search) there is a jump to the beginning of the list using the method toFirst () required. Then the request helps hasAccess () to ask whether a list element is still available or by continuing through the list with the method next () the end of the list has already been reached.

If the string list from the previous section is used as a basis, the output of the loop is: Babsi -> Franz -> Susi -> END!

l.toFirst (); while (l.hasAccess ()) {Strings = l.getContent (); System.out.print (s + "->"); l.next ();} System.out.println (" END!");

Modify a list

For the next example, let's imagine a music collection in the objects of the class title to get managed. A rating between 1 and 5 is given for each title object, which is determined by the method getRating () can be requested.

The loop then goes through the list of all title objects and deletes with the method remove () those titles that have received a rating of 1. In addition, the number of deleted objects is shown in the variable counter counted in.

l.toFirst (); intcounter = 0; while (l.hasAccess ()) {Titelt = l.getContent (); if (t.getEvaluation () == 1) {l.remove (); counter ++;} else { l.next ();}}

Insert into a sorted list

Sorting a list can sometimes also be useful. In our example of the music collection, the title objects could be sorted according to the rating. So that the sorting of the list is not lost, the user of the music collection must be provided with his own method for the sorted insertion of a new title.

The loop is run through until a title is found that has a higher or the same rating as the new title. At this point, the associated title object with the method insert inserted before the current list object.

publicvoidfuegeTitelSortiertEin (Titelt, Listl) {l.toFirst (); while (l.hasAccess ()) {Titelaktuell = l.getContent (); if (t.getEvaluation () <= aktuell.getEvaluation ()) {l.insert ( t); return;} else {l.next ();}} l.append (t);}

Stack and Queue

As a special case of the list, the stack and queue are very similar, which is why they are often discussed together. The queue is a FIFO data structure (first in, first out) - the objects are managed in the order in which they were inserted into the data structure. Direct access is only available to the foremost element of the snake (the head), it is always inserted at the back (at the end of the snake). The stack, on the other hand, is referred to as a LIFO data structure (last in, first out). Here, new objects are always placed on top of the stack; direct access is also only available to the top object of the stack.

Build a stack

As with a list, when creating a stack, you first have to specify the class of the objects that are to be managed in the stack. In the following example three strings are placed on the stack. The LIFO structure results in the sequence seen from top to bottom on the stack Hans - Maria - Manfred.

Strings1 = "Manfred"; Strings2 = "Maria"; Strings3 = "Hans"; Stack s = newStack (); s.push (s1); s.push (s2); s.push (s3 );

Go through a stack

The stack can be easily traversed from top to bottom with a loop.

Note

The stack is reduced in the process, i.e. access to the objects is lost. If this is undesirable, the individual objects must be cached in a different data structure during the run.

while (! s.isEmpty ()) {Current string = s.top (); System.out.println (current); s.pop ();}

Build a queue

As with a list, when creating a queue, you must first specify the class of the objects that are to be managed in the queue. In the example below, three strings are inserted into the queue. The sequence results from the FIFO structure in the queue Manfred - Maria - Hans.

Strings1 = "Manfred"; Strings2 = "Maria"; Strings3 = "Hans"; Queue s = newQueue (); s.enqueue (s1); s.enqueue (s2); s.enqueue (s3 );

Run through a queue

A snake can easily be traversed from front to back with a loop.

Note

The queue is dismantled, i.e. access to the objects is lost. If this is undesirable, the individual objects must be cached in a different data structure during the run.

while (! s.isEmpty ()) {String current = s.front (); System.out.println (current); s.dequeue ();}