Skip to main content

Java collection series - LinkedList

One of the general purpose implementations of the List interface is LinkedList.

Interfaces implemented - List, Queue, Deque, Collection, Iterable, Cloneable, Serializable

Classes extends from - AbstractCollection, AbstractList, AbstractSequentialList

Structurally, it maintains a nested private static class Node using which the doubly linked list is implemented.

Features
  • sequential access data structure (NO random access)
  • non-synchronized data structure (Collections.synchronizedList() can be used to reverse the behavior)
  • Iterator and ListIterator returned from LinkedList are fail-fast (throws ConcurrentModificationException when the structure changes by any method other than the iterators' methods)
  • insertion order is retained in LinkedList
  • has seven optional operations - clone, addFirst, getFirst, removeFirst, addLast, getLast, and removeLast
How good is the performance?
  • O(n) when it comes to search as the LinkedList maintains a doubly linked list which needs traversal through all the elements to find an entry
  • O(1) for insertion and deletion as its just a matter for adding and removing a node and adjusting the two pointers of that node. 
Memory print of LinkedList is high as it needs to maintain the element data of the list along with two pointers for the neighbour nodes.

Comments

Post a Comment

Popular posts from this blog

Working in India

The day I started working in SRA India(Indian arm of Japan's Software Research Associates, Inc ), I never thought that I world become an onsite team member in just one and half years. Because, the branch was very small & it was very illogical for a novice like me to think of an onsite tour that time. But the fact was that they would make you do your work in almost Japanese style. The very first day I started coding in SRA India, I was told that the Japanese were simply put - perfectionists. This simple word had a very large inner meaning. The code that you wrote should be totally bug free, robust, modifiable without introducing regression etc. The first project I was assigned to, it took a hell lot days to prepare only the detailed design(Java Doc) for a very tiny function, every molecular level detail was described on that. But somehow I made myself adjusted to such work environment. My performance was good in my batch. And in one day, one of my managers told me of an onsite a...
Post a Comment
Read more

Java collection series - miscellaneous

Java Vector is a legacy class. And it is significantly faster in comparison to a list obtained through Collections.synchronizedList(). Vector has loads of legacy operations and hence the manipulations in Vector needs to be done through the List interface, otherwise you won't be able to replace the implementation at a later time. Arrays.asList() is better choice if the list is of fixed size and any kind of size mutation of the collection results in UnsupportedOperationException. The underlying array is updated whenever the list is updated (or vice-versa), but the array reference isn't retained. Collections.nCopies() is another convenient mini-implementation which can be useful in two ways - initialize a newly created list with n null values (need not be only null values) -  new ArrayList (Collections.nCopies(1000, (Type)null)  grow an existing list -  lovablePets.addAll(Collections.nCopies(69, "fruit bat")) Collections.singleton()/Collectio...
Post a Comment
Read more

DB transaction ACID properties

DB transaction is a combination of different operations. If not performed in a proper manner, different transactions working on the same data at the same time may leave the data in corrupted state, effecting the application. In this article, I am going to illustrate DB transaction ACID properties through an example of money transfer application between two different accounts A and B. To begin with, lets suppose that accounts A and B both have initial balance of $100. ACID stands for Atomicity , Consistency , Isolation and Durability . Let's try to understand these one by one. Atomicity : This is the property that mandates that if a transaction is started, either all the operations which are part of the transaction need to be completed by end of the transaction completion as a single unit of work or none of the operations needs to be completed. It is maintained by transaction management component. If a debit of $10 is made from account A, then the corresponding credit of $10 al...
Post a Comment
Read more