Skip to main content

Linked List in Java - Collections Framework- DSA

Gist:

A Linked list is dynamic array where a group of object can be stored while following the insertion order and allow duplicates, the 2 type of linked list is singly and double linked lists, the default one is single linked list where the elements can be traversed only in forward direction this is because unlike array here the elements are stored at random locations and only the node of each element knows the address of the next element. A simple example would be our circut board here a point X may be connection to Y and Y connectioned to pont Z here the insertion order is preserved and we can know the next point only by following the signals from the previous point.

Same as the example but in Linked list each element has 2 parts in singly linked list where 1 part is the node with the adress to the next node and the other which is the actua data of that element like a post letter the envelop has the address and inside the contents. but in doubly linked list there are 3 parts 2 of them are nodes which has the address of previous and next element and the other one is the actual data of that element.

The insertion or deletion are in constant time so compared to arrayList the mega process will be avoided. 


Hierarchical order





Type of constructors

  • Empty argument constructor or the default constructor is the same as invoking any other objectobjectobjectobject here a new linked list object will be careated, do note that there is no scope for reserving memory for the number of elements as we add new element the size is maintained dynamically a new Li ked list is empty list. 

    LinkedList = new LinkedLis() ;

  • Conversion of other Collections like ArrayList, Vector, etc...to an linked List is possible with the following constructor.

  • LinkedList arraysFromVector = new LinkedList( VariableNameOfTheCollection );

  • //here any collection will be converted into an Linkedlist

Important Points

  • By default an empty LinkedList is created. 
  • Is Dynamically Growable and Shrinkable. 
  • Heterogeneous Objects are allowed.
  • There is no initial capacity 
  • No load factor is applicable here. 
  • Order of insertion is preserved
  • We can also use generic data-type such that the array acts like a homogenous.
  • Random acess interface is not implemented. 
  • Ideal if the operations are Insertion or deletion. 

Implementing Interfaces

  • Serializable
  • Cloneable
  • Iterable <E>
  • Collection <E>

Methods available to only the Arraylist object. 

  • .addFirst(Element) -> adds the element in the front of the ArrayList. 
  • .addLast(Element) -> add an element in the last part of the ArrayList. 
  • getFirst() --> returns the Object at the front of the Linked List. 
  • getLast() --> returns the last object in the linked list.
  • removeFirst() -> returns the object in the first and removes it from the linked list
  • removeLast() --> returns the last objects and removes the object from the linked list. 
Pros Cons
Ideal if insertion or deletion operations are more. Worst if there are lots of search operations as it needs to iterate through all the other elements. 
By default the elements can be traversed through forwad direction. Java LinkedList class is non-synchronized. 
Can hold duplicate elements. Does not implement random access interface.
Can hold null values.
The process of insertion or deletion is simple and fast.
Labels:

Comments

Post a Comment

Popular posts from this blog

Introduction to Primitives - Java

2. Overview: There are eight primitive data types byte, short, int, long, float, double boolean, char. These eight data types store values as raw instead of Objects these primitives help to save memory to a great extent and simplify other processes as they are directly stored in the stack. Data Type Size(in bits) Minimum Range Maximum Range byte 8 -128 127 short 16 -32768 32767 int 32 -2147483648 2147483647 long 64 -9223372036854775808 9223372036854775807 float 32 -3.4e38 to -1.4e-45 1.4e-45 to 3.4e38 double 64 -1.8e308 to -4.9e-324 4.9e-324 to 1.8e308 boolean 1 - - char 16 space 65535 byte A byte has the capacity of 8 bits or 1 byte and it can store numbers between -2 7 and 2 7 -1 or simply -128 to 127. This is very useful while deali...
Post a Comment
Read more

Chocolate Feast - Problem Solving - Hacker Rank Solution.

The expectation is to find the total number of choclate one can consume by taking full advantage of the offer, Here there are 3 inputs n which holds the value of initial amount of money for buying choclate, c is the cost price of each candy if paid by cash and m is the exchange rate for the candy. Inputs n Initial cash to buy candy. c Coast of each candy if paid by cas.h m Exchange rate for a new candy in offer. The initial count of choclate will be the cash / coast and the wrappers in hand will be the same value of choclate, and from there we loop through until the wrap count is less than the exchange rate, inside the loop the choclate count will still hold the same fourmula as before but divided with exchange rate. The wrap count is the tricky part... the wrap will be wrap/ exchange rate(the no. choclate) + the remainder of this division(THIS IS VERY IMPORTANT) because for example if the count of wrapper is 3 and the exchange rate is 2 you can only buy 1 c...
Post a Comment
Read more

Collection Interface - Java Collections Framework - DSA

Most people consider the collection as the root interface of Collections Framework and it is true to a great extent but another part of Collections Framework is Map Interface, we will see that later, Most Common methods which are applicable to all collections are defined in this interface for example add() to add an element, size() to get the size and much more, below is a table of most common methods. Hierarchey of the Collection Interface. The Parent of Collection Interface is Iterator Interface and the Collection is base class for List Interface, Set Interface and Queue Interface, the respective classes which impliments either of the sub classes will also implement the defined methods from the Collection Interface, below are some of the commonly used methods. Defined Methods: Method Description add() This method returns a Boolean value true if it inserts the specified element in this collection....
Post a Comment
Read more