Summary ArrayList
with ArrayDeque
are preferable in many more use-cases than LinkedList
. If you're not sure — just start with ArrayList
.
TLDR, in ArrayList accessing an element takes constant time [O(1)] and adding an element takes O(n) time [worst case]. In LinkedList adding an element takes O(n) time and accessing also takes O(n) time but LinkedList uses more memory than ArrayList.
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), but O(1) when index = 0
or index = list.size() - 1
(in this case, you can also use getFirst()
and getLast()
). One of the main benefits of LinkedList<E>
add(int index, E element)
is O(n) (with n/4 steps on average), but O(1) when index = 0
or index = list.size() - 1
(in this case, you can also use addFirst()
and addLast()
/add()
). One of the main benefits of LinkedList<E>
remove(int index)
is O(n) (with n/4 steps on average), but O(1) when index = 0
or index = list.size() - 1
(in this case, you can also use removeFirst()
and removeLast()
). One of the main benefits of LinkedList<E>
Iterator.remove()
is O(1). One of the main benefits of LinkedList<E>
ListIterator.add(E element)
is O(1). 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)
LinkedList<E>
allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n) (n/4 steps) on average, though O(1) for index = 0
.
ArrayList<E>
, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList
is O(n) in the worst case but constant on average.
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.)
The main benefits of using a LinkedList
arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList
means following the links in O(n) (n/2 steps) for worst case, whereas in an ArrayList
the desired position can be computed mathematically and accessed in O(1).
Another benefit of using a LinkedList
arises when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList
. Note that ArrayDeque
may be a good alternative to LinkedList
for adding and removing from the head, but it is not a List
.
Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList
has more overhead since pointers to the next and previous elements are also stored. ArrayLists
don't have this overhead. However, ArrayLists
take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.
The default initial capacity of an ArrayList
is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList
with a higher initial capacity.
If the data structures perspective is used to understand the two structures, a LinkedList is basically a sequential data structure which contains a head Node. The Node is a wrapper for two components : a value of type T [accepted through generics] and another reference to the Node linked to it. So, we can assert it is a recursive data structure (a Node contains another Node which has another Node and so on...). Addition of elements takes linear time in LinkedList as stated above.
An ArrayList, is a growable array. It is just like a regular array. Under the hood, when an element is added at index i, it creates another array with a size which is 1 greater than previous size (So in general, when n elements are to be added to an ArrayList, a new array of size previous size plus n is created). The elements are then copied from previous array to new one and the elements that are to be added are also placed at the specified indices.
The use of scriptlets (those <% %>
things) in JSP is indeed highly discouraged since the birth of taglibs (like JSTL) and EL (Expression Language, those ${}
things) way back in 2001.
The major disadvantages of scriptlets are:
- Reusability: you can't reuse scriptlets.
- Replaceability: you can't make scriptlets abstract.
- OO-ability: you can't make use of inheritance/composition.
- Debuggability: if scriptlet throws an exception halfway, all you get is a blank page.
- Testability: scriptlets are not unit-testable.
- Maintainability: per saldo more time is needed to maintain mingled/cluttered/duplicated code logic.
Sun Oracle itself also recommends in the JSP coding conventions to avoid use of scriptlets whenever the same functionality is possible by (tag) classes. Here are several cites of relevance:
From JSP 1.2 Specification, it is highly recommended that the JSP Standard Tag Library (JSTL) be used in your web application to help reduce the need for JSP scriptlets in your pages. Pages that use JSTL are, in general, easier to read and maintain.
...
Where possible, avoid JSP scriptlets whenever tag libraries provide equivalent functionality. This makes pages easier to read and maintain, helps to separate business logic from presentation logic, and will make your pages easier to evolve into JSP 2.0-style pages (JSP 2.0 Specification supports but de-emphasizes the use of scriptlets).
...
In the spirit of adopting the model-view-controller (MVC) design pattern to reduce coupling between the presentation tier from the business logic, JSP scriptlets should not be used for writing business logic. Rather, JSP scriptlets are used if necessary to transform data (also called "value objects") returned from processing the client's requests into a proper client-ready format. Even then, this would be better done with a front controller servlet or a custom tag.
How to replace scriptlets entirely depends on the sole purpose of the code/logic. More than often this code is to be placed in a fullworthy Java class:
If you want to invoke the same Java code on every request, less-or-more regardless of the requested page, e.g. checking if a user is logged in, then implement a filter and write code accordingly in doFilter()
method. E.g.:
public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws ServletException, IOException {
if (((HttpServletRequest) request).getSession().getAttribute("user") == null) {
((HttpServletResponse) response).sendRedirect("login"); // Not logged in, redirect to login page.
} else {
chain.doFilter(request, response); // Logged in, just continue request.
}
}
When mapped on an appropriate <url-pattern>
covering the JSP pages of interest, then you don't need to copypaste the same piece of code overall JSP pages.
If you want to invoke some Java code to process a GET request, e.g. preloading some list from a database to display in some table, if necessary based on some query parameters, then implement a servlet and write code accordingly in doGet()
method. E.g.:
protected void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
try {
List<Product> products = productService.list(); // Obtain all products.
request.setAttribute("products", products); // Store products in request scope.
request.getRequestDispatcher("/WEB-INF/products.jsp").forward(request, response); // Forward to JSP page to display them in a HTML table.
} catch (SQLException e) {
throw new ServletException("Retrieving products failed!", e);
}
}
This way dealing with exceptions is easier. The DB is not accessed in the midst of JSP rendering, but far before the JSP is been displayed. You still have the possibility to change the response whenever the DB access throws an exception. In the above example, the default error 500 page will be displayed which you can anyway customize by an <error-page>
in web.xml
.
If you want to invoke some Java code to process a POST request, such as gathering data from a submitted HTML form and doing some business stuff with it (conversion, validation, saving in DB, etcetera), then implement a servlet and write code accordingly in doPost()
method. E.g.:
protected void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
String username = request.getParameter("username");
String password = request.getParameter("password");
User user = userService.find(username, password);
if (user != null) {
request.getSession().setAttribute("user", user); // Login user.
response.sendRedirect("home"); // Redirect to home page.
} else {
request.setAttribute("message", "Unknown username/password. Please retry."); // Store error message in request scope.
request.getRequestDispatcher("/WEB-INF/login.jsp").forward(request, response); // Forward to JSP page to redisplay login form with error.
}
}
This way dealing with different result page destinations is easier: redisplaying the form with validation errors in case of an error (in this particular example you can redisplay it using ${message}
in EL), or just taking to the desired target page in case of success.
If you want to invoke some Java code to control the execution plan and/or the destination of the request and the response, then implement a servlet according to the MVC's Front Controller Pattern. E.g.:
protected void service(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
try {
Action action = ActionFactory.getAction(request);
String view = action.execute(request, response);
if (view.equals(request.getPathInfo().substring(1)) {
request.getRequestDispatcher("/WEB-INF/" + view + ".jsp").forward(request, response);
} else {
response.sendRedirect(view);
}
} catch (Exception e) {
throw new ServletException("Executing action failed.", e);
}
}
Or just adopt an MVC framework like JSF, Spring MVC, Wicket, etc so that you end up with just a JSP/Facelets page and a JavaBean class without the need for a custom servlet.
If you want to invoke some Java code to control the flow inside a JSP page, then you need to grab an (existing) flow control taglib like JSTL core. E.g. displaying List<Product>
in a table:
<%@ taglib uri="http://java.sun.com/jsp/jstl/core" prefix="c" %>
...
<table>
<c:forEach items="${products}" var="product">
<tr>
<td>${product.name}</td>
<td>${product.description}</td>
<td>${product.price}</td>
</tr>
</c:forEach>
</table>
With XML-style tags which fit nicely among all that HTML, the code is better readable (and thus better maintainable) than a bunch of scriptlets with various opening and closing braces ("Where the heck does this closing brace belong to?"). An easy aid is to configure your web application to throw an exception whenever scriptlets are still been used by adding the following piece to web.xml
:
<jsp-config>
<jsp-property-group>
<url-pattern>*.jsp</url-pattern>
<scripting-invalid>true</scripting-invalid>
</jsp-property-group>
</jsp-config>
In Facelets, the successor of JSP, which is part of the Java EE provided MVC framework JSF, it is already not possible to use scriptlets. This way you're automatically forced to do things "the right way".
If you want to invoke some Java code to access and display "backend" data inside a JSP page, then you need to use EL (Expression Language), those ${}
things. E.g. redisplaying submitted input values:
<input type="text" name="foo" value="${param.foo}" />
The ${param.foo}
displays the outcome of request.getParameter("foo")
.
If you want to invoke some utility Java code directly in the JSP page (typically public static
methods), then you need to define them as EL functions. There's a standard functions taglib in JSTL, but you can also easily create functions yourself. Here's an example how JSTL fn:escapeXml
is useful to prevent XSS attacks.
<%@ taglib uri="http://java.sun.com/jsp/jstl/functions" prefix="fn" %>
...
<input type="text" name="foo" value="${fn:escapeXml(param.foo)}" />
Note that the XSS sensitivity is in no way specifically related to Java/JSP/JSTL/EL/whatever, this problem needs to be taken into account in every web application you develop. The problem of scriptlets is that it provides no way of builtin preventions, at least not using the standard Java API. JSP's successor Facelets has already implicit HTML escaping, so you don't need to worry about XSS holes in Facelets.
See also:
Best Answer
Use HttpComponentsClientHttpRequestFactory instead of SimpleClientHttpRequestFactory.
Also add dependency to 'org.apache.httpcomponents:httpclient.
HttpComponentsClientHttpRequestFactory ccan read body when status is 401.