Is ArrayList and linked list same?

ArrayList is a resizable array usually found in java. util packages and stands a difference with built-in array due to modification of size and comes with more derived elements. LinkedList is known for its data structure linearity and is not stored at a location contagious like ArrayList. The differences in them make it unique to use in different algorithm situations in Java and another coding.  

The main difference between ArrayList and LinkedList is that ArrayList falls under the category of collection framework of dynamic arrays distinct to standard arrays whereas LinkedList exercises LinkedList Data Structure within its class with variations in every element embraced with a data and address wedge. 

Is ArrayList and linked list same?

As said that ArrayList takes an immense part in the collection framework, which leads to dynamic arrays in Java performed by various elements and operations. There are always some basic operations performed in ArrayList like adding and changing elements and inherited AbstractList class. The initialization of size in ArrayList tends to increase and shrink based on the collection. 

LinkedList is known for its dynamic size and the notion of easy insert and deletes, unlike ArrayList. LinkedList is represented by a pointer to the head (node) to make sure whether it is impactful or null. They are also linked through addresses and are often preferred over elements of the array.

Parameter of ComparisonArrayList LinkedList 
UsageA dynamic array is used to store elements internally. A double-linked list is used to store elements internally. 
ManipulationManipulation is slow and takes more time. Manipulation is faster and takes the least time. 
Implementation ArrayList implements only List. LinkedList implements List and Queue. 
Access ArrayList is better when an application wants to store and access data.  LinkedList works faster in the manipulation of the stored data. 
PerformanceArrayList performs 0(1). LinkedList performs 0(n). 

What is ArrayList? 

ArrayList uses its distinctive dynamic array for storing the elements with no size limit. This improvises that one can add and remove these elements anytime required. ArrayList is much more flexible than the substantial array used in java before and now, Arraylist is found in java. util package. Moreover, the ArrayList uses an array data structure and so maintains an index-based system for its elements. This amplifies in making it faster for searching an element in the list.  

ArrayList has some duplicate elements also that are implemented and acts on the list. This happens so that we can use all the methods of the List interface here as its key features. The ArrayList also manages and maintains the internal order insertion and inherits the AbstractList but is non-synchronized. An important fact about ArrayList is its random access due to the work of an array based on an index.  

ArrayList() is used to build an empty array list, ArrayList(Collectionc) is used to build an array list initialized by the elements of collection “c”, and ArrayList(int capacity) is used in array list where there is specialized initial capacity. 

It is a tat bit slower in manipulation compared to LinkedList because whenever the element is omitted it causes many shifting which affects it. Hence, it extends in sequential order for the list interface. 

A LinkedList is connected through links in a sequence of data structures. It contains items that are linked with one another from one end to another to work sequentially and in every manner.LinkedList is though more preferable to an array and is second most preferably used after array. LinkedList implements a doubly linked list. It requires the crosspiece through all the elements for searching it. LinkedList is widely used.

To understand the concept of LinkedList certain terms require to be understood. The terms are Link where each link in the linked list can store data known as elements. There is Next where each link is connected from each end in the data. At last, there is LinkedList which is connected from one end link to the first link for the LinkedList to work, which is often referred to as First. 

There are various types of LinkedList such as Simple LinkedList for item navigation forward only, Double LinkedList for navigation of items forward and back, and Circular Linked List to form a circular link from the last item link to the first element and next and e first element link to the last element and previous. The basic operations of LinkedList for elements are insertion, deletion, display, search and delete. 

Main Difference between ArrayList and LinkedList: 

  1. In LinkedList elements can be added indefinitely whereas in an ArrayList elements usually get filled or gets resized. 
  2. It is easier to remove elements from the LinkedList whereas in ArrayList it is not easy as it leaves empty spaces which occupy computer memory for no use. 
  3. ArrayList allows random access to elements contained internally. LinkedList, however, only allows sequential access to the elements. 
  4. LinkedList used more storage space in the computer’s memory compared to ArrayList as each node in the list contains both the data and reference link to the next mode. It is unlike in ArrayList. 
  5. ArrayList should be used for small lists, where almost every number of items on the list is known. On the other hand, LinkedList should be used for large lists of data where there is a change in the total number of items. 

Conclusion:

Though both ArrayList and LinkedList implements List Interface and the insertion order is maintained well, there are vast differences between them that keep them divided for different java packages. These differences make one more preferable than the other based on the situations required, algorithms runtime. Their differences are vivid on search, maintenance, the requirement of frequent addition, deletion, frequency of search operations, and more. It is the differences that make java and other coding easier and choice as per requirements.

References:

Are you looking to know the difference between ArrayList vs. LinkedList 

Lists provide easy ways to manipulate, store, and retrieve data. Lists are used extensively in all programming languages like C, C++, Java, Python, etc.… The list is an interface extended from the generic Collection interface. 

In this article, we will learn about ArrayList and LinkedList is used in Java, with examples and then go on to compare both of them to understand how each of these is used for different situations. 

What is ArrayList?

ArrayList is the simplest list that can store different types of data. To understand ArrayList, consider the following data stored in an array – 

String[] names = new String[5];names[0] = "Mac";names[1] = "Jony";names[2] = "Mary";names[3] = "Donald";

names[4] = "Phoebe";

where Student is a class that holds information about students of a college like a name, age, subject, average marks, email id, gender, and whether they have distinguishing marks or not.

Details of each Student are stored in an array, names. The array size is fixed as 5. However, what happens if there are more students than 5?

With ArrayList, this problem will not occur. ArrayList is a dynamic array, which grows in size as the number of elements increases.

ArrayList namesList = new ArrayList();namesList.add("Mac");namesList.add("Jony");namesList.add("Mary");namesList.add("Donald");

namesList.add("Phoebe");

As we see, there is no initial size given to the list. It can just add elements as the list grows. In fact, any type of manipulation is easy with ArrayList. If you want to access any element of the list, you can easily get it using the index. The first index is always zero. Suppose, you want to replace the name “Mary” to “Maryln”, you could do the following –

namesList.remove(namesList.get(2));
namesList.add(2, "Maryln");

We have removed the previous name and added the new one in the same place. You can also add elements at any location. For example,

namesList.add(2, "Joseph");

This will not replace ‘Maryln’ but will move it to the next index. If you print the list you will get –

[Mac, Jony, Joseph, Maryln, Donald, Phoebe]
 0   1 2       3 4        5

This means to accommodate ‘Joseph’, all the other elements have been shifted to the right. Same way, when we removed Mary, all the other elements had to be moved to the left.

Duplicate values are perfectly acceptable in ArrayList. If we add another element with the same name, the list size will grow and the value will be displayed without any issue.

ArrayList implements the List interface which in turn extends the interface Collection. The collection is extended by the Iterable interface. The hierarchy of ArrayList is as follows

Is ArrayList and linked list same?

Source: Javadocs

It is also easy to sort objects in ascending or descending order with ArrayList using the method sort of the Java .util.Collections class.

ArrayList is not synchronized, which means if multiple threads change a list at the same time, the result could be unpredictable. We can also add a value of null to an ArrayList, which will be displayed at its position as “null”.

LinkedList is a linear data structure where each element of the list is referred to as a node that contains the element value and the pointer to the previous and next node. In Java, LinkedList is implemented as a doubly-linked list internally (although, Java also supports Singly Linked List). In a doubly-linked list, each node has a reference to its next and previous nodes, other than containing the node’s actual value. Here is a quick diagram that represents a doubly linked list –

Is ArrayList and linked list same?

The demarcation on the left of each item indicates previous pointer, and the demarcation on the right indicates the next pointer. Item 1 has the previous node pointer as null, whereas next points to item 2 in the list. item 2 has a previous pointer to item 1 and next to item 3. Since item 3 is the last element, the next pointer (of item3) is null and the previous pointer (of item3) is the same as the next pointer of item 2. This means both are same values and determine the sequence of the list.

The other types of LinkedList are Singly Linked List and Circular Linked List.

LinkedList has same features as ArrayList. For example, you get can objects using index using the get() method, you can add, remove elements and store as many objects as you need. While coding, you will not see much difference between ArrayList and LinkedList. Our earlier example, when executed with LinkedList is as follows –

LinkedList lnkdlst = new LinkedList();lnkdlst.add("Mac");lnkdlst.add("Jony");lnkdlst.add("Mary");lnkdlst.add("Donald");lnkdlst.add("Phoebe");lnkdlst.add("Mac");System.out.println("The first element is - " + lnkdlst.get(0));System.out.println("The last element is - " + lnkdlst.get(lnkdlst.size()-1));Collections.sort(lnkdlst);System.out.println("Sorted linked list - " + lnkdlst);lnkdlst.add(1, "Joana");lnkdlst.remove("Mac");

System.out.println("After additions and deletions - " + lnkdlst);

As you will notice, we can add duplicates, and also the name ‘Joana’ has been added at the index position ‘1’. If we don’t specify any index, elements are added to the end of the list. The insertions can be done anywhere in a LinkedList without having to change the index of every single item – only the pointer needs to be updated – thus making it faster.

Here is the sample output if you run the above code -

The first element is - MacThe last element is - MacSorted linked list - [Donald, Jony, Mac, Mac, Mary, Phoebe, Steve]

After additions and deletions - [Donald, Jony, Mac, Mary, Phoebe, Steve, Joana, null]

Just like ArrayList, LinkedList is also not synchronized and can hold null values.

Here is the hierarchy of LinkedList –

Is ArrayList and linked list same?

Source – Javadocs

Here comes the first difference – whereas ArrayList only implements List, LinkedList implements List and Queue both! Therefore, LinkedList is an implementation of both Deque and List and it inherits certain methods of Deque as well. One common example of that is the descendingIterator() method which is not present in ArrayList. This method reverses the order of the list and returns an iterator i.e. the elements will be shown from tail to head –

Iterator itr = lnkdlst.descendingIterator();while (itr.hasNext()) {             System.out.println("Value is : " + itr.next());

      }

However, this doesn’t change the original linked list. 

What is Deque?

Deque is a double-ended queue. By implementing Deque, LinkedList can be used as a stack, list or queue. If you want to see more about this additional functionality of LinkedList, this page has some great insights to offer.

When to use an Array List?

If the project or application requires more of a search operation than to perform updates like add or delete then one must use array list over linked list as it requires a constant time i.e, O(1) time complexity for a search operation whereas a linked list has O (n/2) complexity. 

If the project or application requires more of an update operation like adding or deleting an element than to perform search then one must use linked list over array list as it requires a constant time for an update operation. Linked list along with manipulation also offers a dequeue 

Operation which an array list does not implement. Linked List class has a Deque interface to get  the functionality of a double ended queue in LinkedList. The ArrayList class doesn't implement the Deque interface.

Now that we have some knowledge of both, let us come to the differences:

ArrayListLinkedList
Implemented as a dynamic array using an array of objects to store elements sequentiallyImplemented as a doubly-linked list (in Java), consists of pointers to previous and next nodes.
Implements the List interfaceImplements List and Deque (double ended Queue) which gives it additional functionality
Faster to store and access data using indexRetrieval and storage are a bit slow as the list has to traverse through each node to identify the correct one.
Removal and addition are slow because all the other items have to be shifted left or right accordingly.Faster and more efficient for data manipulation like adding and removing elements from any part of the list
Removing an item while iterating through the list is slower because all the other elements have to be shuffled to fill the gaps in the list created by the removed elementsRemoving an element while iterating is simple and only the next and previous nodes have to be adjusted. 
You can specify the size of the initial ArrayList using ArrayList(int capacity) constructor. The size can still grow later, however, an initial amount can be set. ArrayList works even faster if the capacity specified is not exceeded.LinkedList supports only no-argument constructor –LinkedList()
No provision for getting the methods of Queue or Deque.Implements Deque, that provides descendingIterator() that returns iterator having list value in reverse sequence. Same way methods like peek(), poll() and offer() (and its variants) are available so that the list function as a queue.
ArrayList cannot be used as a Stack.As Deque also supports the methods push(), peek() and pop(), LinkedList can be used as a Stack.

Conclusion

While there is no right or wrong answer to this question, it certainly depends on your requirements. If you are not going to modify the list too much once it is created, ArrayList is a better choice. If there is a lot of manipulation involved, LinkedList is faster. There are many other features that LinkedList has because it implements a Deque interface, which can be an added advantage. Both the data structures follow the same principle in other languages like C or C++. Learn more about data structures here. 

People are also reading: