Tags

, , , , , ,

Discrete Mathematical Algorithm, and Data Structures

Discrete Mathematical Algorithm, and Data Structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

Which is faster? ArrayList, or LinkedList?

It’s not a million dollar question. We all know that LinkedList is faster. But, do you know the reason.

Here is an explanation.

As we have seen that the two most natural ways of storing sequences in computer memory are arrays and linked lists. ArrayList is an ADT that uses all concepts of handling Arrays with more flexibility. That is why, the time complexity is same for the both.

In LinkedList, it does not work that way. We usually model the memory as a sequence of memory cells, each of which has a unique address. An array or ArrayList is a contiguous piece of memory. Each cell of the memory stores one object, which is a part of the sequence stored in an Array or an ArrayList.

In a singly LinkedList two successive memory cells are allocated for each object of the sequence. Two memory cells form a node of a sequence. The first cell stores the object and the second cell stores a reference to the next node of the list.

In the next node there is two memory cells, and the previous node points to the first memory cell of the next node.

In a doubly linked list, the mechanism changes. Then we not only store a reference to the successor of each element, but we need to have a reference to its predecessor. It means each node should have three successive memory cells. We will discuss it in detail later.

At present, we will see how a singly LinkedList works.

 

//code 
package fun.sanjibsinha.nodepackage;

public class NodeClass {

private int dataElement;
private NodeClass next;

public NodeClass(){
dataElement = 0;
next = null;
}

public NodeClass(int dataInt){
this.dataElement = dataInt;
this.next = null;
}

public NodeClass(int dataElement, NodeClass node){
this.dataElement = dataElement;
this.next = node;
}

public void insertAfter(NodeClass node){
NodeClass temporaryNode = this.next;
this.next = node;
node.next = temporaryNode;
}

public NodeClass nextNode(){
return this.next;
}

public void displayDataElement(){
System.out.println(this.dataElement);
}

}


package fun.sanjibsinha.nodepackage;

public class DisplayLinkedList {

public static void main(String[] args) {

NodeClass headNode;
NodeClass nextNodeOne;
NodeClass nextNodeTwo;
NodeClass nextNodeThree;
NodeClass currentNode;

headNode = new NodeClass(10);

nextNodeOne = new NodeClass(120);
headNode.insertAfter(nextNodeOne);

nextNodeTwo = new NodeClass(1200);
nextNodeOne.insertAfter(nextNodeTwo);

nextNodeThree = new NodeClass(12000);
nextNodeTwo.insertAfter(nextNodeThree);

currentNode = headNode;
while (currentNode != null){
currentNode.displayDataElement();
currentNode = currentNode.nextNode();
}
}
}

 

In the above code we have implemented the ADT of a singly LinkedList, where we have only added or inserted next node until it reaches the NULL value.

 

//output
10
120
1200
12000

 

At the same time we can see a code sample of ArrayList where we have added a few elements. Before moving further, we need to know that ArrayList is an ADT that provides a generic class, which has many useful methods to deal with a collection of data. It also supports different data types. Using the ArrayList methods we could easily add, remove, modify any element. Moreover, we could count the size of the list and based on which we could use the looping construct.

An ArrayList is declared as follows:

ArrayList<T> arrayList = new ArrayList<T>();

Here T is the data type, not the primitive data type, but the Wrapper Class. Let us take a look at some implementations.

//code
//Java
package fun.sanjibsinha;

import java.util.ArrayList;

public class ArrayListExamples {

public static void main(String[] args) {

/**
* ArrayList examples
* ArrayList is an ADT that provides a generic class, which has many useful methods to deal
* with a collection of data. It also supports different data types.
* An ArrayList is declared as follows:
* ArrayList<T> arrayList = new ArrayList<T>();
* Here T is the data type.
*/
ArrayList<String> arrayList = new ArrayList<String>();
arrayList.add("index");
arrayList.add("about");
arrayList.add("contact");
arrayList.add("products");
arrayList.add("sellers");

for (int i = 0; i < arrayList.size(); i++){
System.out.println(arrayList.get(i));
}
}
}

 

We have added a few elements and the output is quite simple.

 

//output of code 6.3
index
about
contact
products
sellers

It always takes more time to add elements to any ArrayList. Specially when we remove any element midway.