Skip to main content

Why LinkedList (Java) sucks? Performance comparison with ArrayList? When to use ArrayList over LinkedList?

Collection is the most used concept in Java after String, in collection framework we are mostly rely on ArrayList and LinkedList for keeping the objects in sequential form. these two are most used implementations of List interface but LinkedList always sucks in performance although LinkedList have some advantages as well. ArrayList is what you want. LinkedList is almost always a (performance) bug.
Why LinkedList sucks:
  1. It uses lots of small memory objects internally to keep connecting the objects, and therefore impacts performance across the process.
  2. Lots of small objects are bad for cache-locality.
  3. Any indexed operation requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if ArrayList was used.
  4. Getting good performance is tricky.
  5. Even when big-O performance is the same as ArrayList, it is probably going to be significantly slower anyway.
  6. It's jarring to see LinkedList in source because it is probably the wrong choice.

Performance Comparison : 
Now we are going to see the performance of the ArrayList and LinkedList in some well known operations:

Operation ArrayList LinkedList


seek front O(1) O(1)


seek back O(1) O(1)


seek to index O(1) O(N)


insert at front O(N) O(1)


insert at back O(1) O(1)


insert after an item O(N) O(1)

LinkedList is almost always the wrong choice, performance-wise. There are some very specific algorithms where a LinkedList is called for, but those are very, very rare and the algorithm will usually specifically depend on LinkedList's ability to insert and delete elements in the middle of the list relatively quickly, once you've navigated there with a ListIterator.
LinkedList can be iterated in reverse direction using descendingIterator() while there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.
When to use which one over another one:
Now come to the conclusion when to use which LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.
As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For LinkedList<E>
  • get(int index) is O(n) (with n/4 steps on average)
  • add(E element) is O(1)
  • add(int index, E element) is O(n) (with n/4 steps on average), but O(1) when index = 0 main benefit of LinkedList<E>
  • remove(int index) is O(n) (with n/4 steps on average)
  • Iterator.remove() is O(1). main benefit of LinkedList<E>
  • ListIterator.add(E element) is O(1) This is one of the main benefits of LinkedList<E>
  • Note: Many of the operations need n/4 steps on average, constant number of steps in the best case (e.g. index = 0), and n/2 steps in worst case (middle of list)
For ArrayList<E>
  • get(int index) is O(1) main benefit of ArrayList<E>
  • add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  • add(int index, E element) is O(n) (with n/2 steps on average)
  • remove(int index) is O(n) (with n/2 steps on average)
  • Iterator.remove() is O(n) (with n/2 steps on average)
  • ListIterator.add(E element) is O(n) (with n/2 steps on average)
  • Note: Many of the operations need n/2 steps on average, constant number of steps in the best case (end of list), n steps in the worst case (start of list)
So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this; they're both constants.)

Comments

Popular Posts

Who is Peter Lynch and what is his philosophy in equity market investment? 25 Golden Rules of the most successful Fund Manager.

Peter Lynch (born January 19, 1944) is an American investor, mutual fund manager, and philanthropist. As the manager of the Magellan Fund at Fidelity Investments between 1977 and 1990, Lynch averaged a 29.2% annual return, consistently more than doubling the S&P 500 stock market index and making it the best-performing mutual fund in the world.During his 13 year tenure, assets under management increased from $18 million to $14 billion. He also co-authored a number of books and papers on investing and coined a number of well known mantras of modern individual investing strategies, such as Invest in what you know and ten bagger. Lynch is consistently described as a "legend" by the financial media for his performance record. Base on his career I have compiled his investing rules here.
25 GOLDEN RULES by @Peter Lynch
1:
Nobody can predict interest rates, the future direction of the economy or the stock market. Dismiss all such forecasts & concentrate on what's actually …

What is wrong with HDFC securities? Are they doing some fraudulent activities or just causing issues with their platform as usually it don't work during market hours?

I have opened a DEMAT account with HDFC Securities in 2019 as HDFC group is well known for the customer services and I also hold a salary account with HDFC Bank, DEMAT account with the following conditions/offers as expressed by the executive. Trading Account Opening Charges (One Time):  ₹999 (At that time it offered on lower price, I forget the exact price) Trading Annual Maintenance Charges AMC (Yearly Fee) : ₹0 Demat Account Opening Charges (One Time) : ₹0 Demat Account Annual Maintenance Charges AMC (Yearly Fee) : ₹750, nil if portfolio value below ₹2 lacs. Equity Delivery: 0.50% Equity Intraday: 0.05% Equity Futures: 0.05% Equity Options: ₹100 per lot or 1% of the premium (whichever is higher) Currency Futures: ₹23 per contract Currency Options: ₹20 per contract Commodity Futures: 0.02% for Intraday / 0.025% for positional Commodity Options: 0.02% for Intraday / 0.025% for positional
It was going good but after 2-3 months I got to know that there are some discount brokers in the market which …

What is sales?

In simple words, "Transfer of ownership in terms of values is known as sales" By scholars, it is defined as "Exchange of a thing(Subject matter) of value with another thing of value, with mutual consent." How the concept evolved? We all know, initially when the civilization was evolving, the concept of barter system came into existence. Barter system says one person gives something in exchange of another thing from another person. Same is happening today but scenario has been changed little bit, the two things are CommodityCurrency Sales is an activity related to selling of goods & services (in given time sometimes). It is not just a process of exchange but it also develops relationships with customers or demand partners. There are cases where companies set sales volume targets for a period(weeks, months or quarters or sometimes years) and have strategies in place. Sales is the final stage in marketing includes 4 P's P- ProductP- PricingP- PlaceP- Promotion
Its…

What is the Difference Between OLA and SLA?

The difference between a Service Level Agreement (SLA) and an Operational Level Agreement (OLA) is what the IT organization as a whole is promising to the customer (SLA), and what the functional IT groups promise to each other (OLA). The SLA can state that "IT will ensure that computer equipment will be maintained". Of course that statement is a generalization that cannot be measured, so perhaps a better statement would be "There will be less than 80 lost man-hours per year due to lack of computer equipment maintenance". or  SLA's are generally an agreement between the IT department/provider and the business, to provide a particular level of service. OLA's are usually agreements between different areas of the IT department/providers, often to provide a particular SLA. For example we can say that,  For an organisation may have a particular SLA that states no more than 100 minutes downtime per quarter. For the IT department to adhere to this, there needs to …

Is investing in the stock market a risk? Tips to reduce the risks?

So Investing in share market is really a great idea since you can gain so much profit. Now the question arises how do we get profit out of stock market? Investing involves risk. Over the long-term, assuming a fairly efficient market, investors will be compensated for taking risk.
However, as the chart (left side) shows, you can also lose an awful lot of money or basically stay flat for long periods of time. Let's start with some basic understanding that when we start driving a car first we get understand the functioning, then features, options then only we start learning the driving. But what if take your car directly on highway.  These are the major difference between real investors and gamblers. Gamblers invest money without knowing the entire functioning and without research. They also have a myth that stock market can double the money within weeks or even in days.  There are some basic guidelines you need to follow before coming into the market. First you need to understand how th…

How i+=j works in Java?It will surprise you?

According to the specification of Java for mathematical operations ,  If the left-hand operand expression is not an array access expression, then:
First, the left-hand operand is evaluated to produce a variable. If this evaluation completes abruptly, then the assignment expression completes abruptly for the same reason; the right-hand operand is not evaluated and no assignment occurs.Otherwise, the value of the left-hand operand is saved and then the right-hand operand is evaluated. If this evaluation completes abruptly, then the assignment expression completes abruptly for the same reason and no assignment occurs.Otherwise, the saved value of the left-hand variable and the value of the right-hand operand are used to perform the binary operation indicated by the compound assignment operator. If this operation completes abruptly, then the assignment expression completes abruptly for the same reason and no assignment occurs.Otherwise, the result of the binary operation is converted to the…

Introduction to IOT? How IOT is going to change the lifestyle of the people?

If we talk about internet, technology, network demand, applications then we will definitely come to a point in our discussion i.e. IoT. As technology is growing, the demand for internet application development is also growing and IoT plays a vital role in developing such applications. IoT stands for Internet of Things. It is an Internet technology connecting devices, machines and tools to the internet by means of wireless technologies. Over 9 billions 'things' connected to the internet as of now and also 'things' connected to the internet are expected to rise beyond 20 billion in near future. IoT is influencing our lifestyle from the way we react to the way we behave. From the Air conditioners that you can control from your smartphones to the smart cars providing the shortest routes or your smart watches which is tracking your daily routine.  What is IoT? IoT is known as Internet of Things which means things and connected to each other and communicating with each other via…