ArrayList and LinkedList in Java

How is ArrayList different from Vector? Why added an ArrayList if there was already a Vector?

  • The Vector class methods are synchronized, but ArrayList is not;
  • By default, Vector doubles its size when the memory allocated for the elements runs out. ArrayList only increases its size by half.

Vector is a deprecated class and its use is deprecated.

How is ArrayList different from LinkedList? In what cases is it better to use the first, and in what cases the second?

ArrayList is an array based list, while LinkedList is a classic doubly linked list based on objects with links between them.

ArrayList:

  • access to an arbitrary element by index in constant time O(1);
  • access to elements by value in linear time O(N);
  • insertion at the end is performed on average in constant time O(1);
  • removing an arbitrary item from the list takes a long time since in this case, all elements located "to the right" are shifted one cell to the left (the real size of the array (capacity) does not change);
  • inserting an element into an arbitrary place in the list takes a lot of time since in this case, all elements that are "to the right" are shifted one cell to the right;
  • minimum storage overhead.

LinkedList:

  • it takes linear time O(N) to get an element by index or value;
  • adding and removing to the beginning or end of the list will take constant O(1);
  • insertion or removal to/from an arbitrary place constant O(1);
  • requires more memory to store the same number of elements, because besides the element itself, pointers to the next and previous elements of the list are also stored.

In general, LinkedList in absolute terms loses out to ArrayList in terms of memory consumption and speed of operations. LinkedList is preferred when you need frequent insert/delete operations or when you need a guaranteed time to add an item to the list.

Which is faster than ArrayList or LinkedList?

It depends on what actions will be performed on the structure.

What's the worst running time for the contains() method for an element that is in a LinkedList?

O(N). The search time for an item is linearly proportional to the number of items in the list.

What's the worst running time for the contains() method for an element that is in an ArrayList?

O(N). The search time for an item is linearly proportional to the number of items in the list.

What's the worst running time for the add() method for a LinkedList?

O(N). Adding to the beginning/end of the list is done in O(1) time.

What's the worst running time for the add() method for an ArrayList?

O(N). Inserting an element to the end of the list takes O(1) time, but if the capacity of the array is insufficient, then a new array with an increased size is created and all elements from the old array are copied into the new one.

If you need to add 1 million elements, what structure are you using?

An unambiguous answer can be given only on the basis of information about which part of the list the elements are being added to, what will then happen to the elements of the list, whether there are any memory or execution speed limitations.

How do you remove elements from an ArrayList? How does the size of the ArrayList change in this case?

When an arbitrary element is removed from the list, all elements to the right are shifted one cell to the left and the real size of the array (its capacity) does not change in any way. The mechanism of automatic "expansion" of the array exists, but there is no automatic "compression", you can only explicitly perform the "compression" with the trimToSize() command.

Read also:


Comments

Post a Comment

Popular posts from this blog

Methods for reading XML in Java

Image
DOM (Document Object Model) - object - reads XML, recreating it in memory in the form of an object structure, while the XML document is represented as a set of tags - nodes. Each node can have an unlimited number of child nodes. Each child can also contain several levels of descendants or none at all. Thus, the result is a kind of tree. Pluses: Easy to program. If there are many objects in XML with cross-references to each other, it is enough to go through the document twice: first time create objects without references and fill in the name-object dictionary, the second time - restore links. If an error occurs in XML, a half-created XML structure remains in memory, which will be automatically destroyed. Suitable for both reading and writing. Minuses: Low speed. Wastes a lot of memory. SAX (Simple API for XML) - event-driven - reads an XML document, responding to emerging events (opening or closing tag, string, attribute) by calling the event handlers provided by the appl...
Read more

XML, well-formed XML and valid XML

Image
XML, the eXtensible Markup Language, is a language with a simple formal syntax, well suited for creating and manipulating documents with programs, and at the same time easy to read and create documents by humans. XML is extensible, it does not fix the markup used in documents, and the developer is free to create markup in accordance with the needs of a particular area, being limited only by the syntax rules of the language. DTD A DTD, Document Type Definition, is a predefined set of rules that defines the relationships between elements and attributes. For example, the DTD for HTML says that the DIV tag must be inside the BODY tag and can appear multiple times, TITLE - in HEAD and only once, and SCRIPT - both there and there as many times as you want. A DTD is usually described directly in the document as a formulation line starting with <!DOCTYPE ... > or in a separate file. Difference between well-formed XML and valid XML Depending on the level of compliance, the document...
Read more

ArrayList and LinkedList in Java, memory usage and speed

Image
How much extra memory is needed when calling ArrayList.add()? If there is enough space in the array to accommodate a new element, then no additional memory is required. Otherwise, a new array is created, 1.5 times larger than the existing one (this is true for JDK above 1.7, in earlier versions the size of the increase is different). How much extra memory is allocated when you call LinkedList.add()? One new instance of the nested Node class is created. How much memory to store one byte primitive in LinkedList? Each LinkedList element stores a link to the previous element, the next element, and a data link. private static class Node<E> { E item; Node<E> next; Node<E> prev; //... } For 32-bit systems, each link is 32 bits (4 bytes). The object (header) of the nested Node class itself takes 8 bytes. 4 + 4 + 4 + 8 = 20 bytes, and since the size of each object in Java is a multiple of 8, so we get 24 bytes. A byte primitive occupies 1 by...
Read more