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 copiedadd(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.
First a disclaimer beforehand: the posted code snippets are all basic examples. You'll need to handle trivial IOExceptions and RuntimeExceptions like NullPointerException, ArrayIndexOutOfBoundsException and consorts yourself.
In case you're developing for Android instead of Java, note also that since introduction of API level 28, cleartext HTTP requests are disabled by default. You are encouraged to use HttpsURLConnection, but if it is really necessary, cleartext can be enabled in the Application Manifest.
Preparing
We first need to know at least the URL and the charset. The parameters are optional and depend on the functional requirements.
String url = "http://example.com";
String charset = "UTF-8"; // Or in Java 7 and later, use the constant: java.nio.charset.StandardCharsets.UTF_8.name()
String param1 = "value1";
String param2 = "value2";
// ...
String query = String.format("param1=%s¶m2=%s",
URLEncoder.encode(param1, charset),
URLEncoder.encode(param2, charset));
The query parameters must be in name=value format and be concatenated by &. You would normally also URL-encode the query parameters with the specified charset using URLEncoder#encode().
The String#format() is just for convenience. I prefer it when I would need the String concatenation operator + more than twice.
Firing an HTTP GET request with (optionally) query parameters
It's a trivial task. It's the default request method.
URLConnection connection = new URL(url + "?" + query).openConnection();
connection.setRequestProperty("Accept-Charset", charset);
InputStream response = connection.getInputStream();
// ...
Any query string should be concatenated to the URL using ?. The Accept-Charset header may hint the server what encoding the parameters are in. If you don't send any query string, then you can leave the Accept-Charset header away. If you don't need to set any headers, then you can even use the URL#openStream() shortcut method.
InputStream response = new URL(url).openStream();
// ...
Either way, if the other side is an HttpServlet, then its doGet() method will be called and the parameters will be available by HttpServletRequest#getParameter().
For testing purposes, you can print the response body to standard output as below:
try (Scanner scanner = new Scanner(response)) {
String responseBody = scanner.useDelimiter("\\A").next();
System.out.println(responseBody);
}
Firing an HTTP POST request with query parameters
Setting the URLConnection#setDoOutput() to true implicitly sets the request method to POST. The standard HTTP POST as web forms do is of type application/x-www-form-urlencoded wherein the query string is written to the request body.
URLConnection connection = new URL(url).openConnection();
connection.setDoOutput(true); // Triggers POST.
connection.setRequestProperty("Accept-Charset", charset);
connection.setRequestProperty("Content-Type", "application/x-www-form-urlencoded;charset=" + charset);
try (OutputStream output = connection.getOutputStream()) {
output.write(query.getBytes(charset));
}
InputStream response = connection.getInputStream();
// ...
Note: whenever you'd like to submit a HTML form programmatically, don't forget to take the name=value pairs of any <input type="hidden"> elements into the query string and of course also the name=value pair of the <input type="submit"> element which you'd like to "press" programmatically (because that's usually been used in the server side to distinguish if a button was pressed and if so, which one).
You can also cast the obtained URLConnection to HttpURLConnection and use its HttpURLConnection#setRequestMethod() instead. But if you're trying to use the connection for output you still need to set URLConnection#setDoOutput() to true.
HttpURLConnection httpConnection = (HttpURLConnection) new URL(url).openConnection();
httpConnection.setRequestMethod("POST");
// ...
Either way, if the other side is an HttpServlet, then its doPost() method will be called and the parameters will be available by HttpServletRequest#getParameter().
Actually firing the HTTP request
You can fire the HTTP request explicitly with URLConnection#connect(), but the request will automatically be fired on demand when you want to get any information about the HTTP response, such as the response body using URLConnection#getInputStream() and so on. The above examples does exactly that, so the connect() call is in fact superfluous.
Gathering HTTP response information
- HTTP response status:
You need an HttpURLConnection here. Cast it first if necessary.
int status = httpConnection.getResponseCode();
HTTP response headers:
for (Entry<String, List<String>> header : connection.getHeaderFields().entrySet()) {
System.out.println(header.getKey() + "=" + header.getValue());
}
HTTP response encoding:
When the Content-Type contains a charset parameter, then the response body is likely text based and we'd like to process the response body with the server-side specified character encoding then.
String contentType = connection.getHeaderField("Content-Type");
String charset = null;
for (String param : contentType.replace(" ", "").split(";")) {
if (param.startsWith("charset=")) {
charset = param.split("=", 2)[1];
break;
}
}
if (charset != null) {
try (BufferedReader reader = new BufferedReader(new InputStreamReader(response, charset))) {
for (String line; (line = reader.readLine()) != null;) {
// ... System.out.println(line)?
}
}
} else {
// It's likely binary content, use InputStream/OutputStream.
}
Maintaining the session
The server side session is usually backed by a cookie. Some web forms require that you're logged in and/or are tracked by a session. You can use the CookieHandler API to maintain cookies. You need to prepare a CookieManager with a CookiePolicy of ACCEPT_ALL before sending all HTTP requests.
// First set the default cookie manager.
CookieHandler.setDefault(new CookieManager(null, CookiePolicy.ACCEPT_ALL));
// All the following subsequent URLConnections will use the same cookie manager.
URLConnection connection = new URL(url).openConnection();
// ...
connection = new URL(url).openConnection();
// ...
connection = new URL(url).openConnection();
// ...
Note that this is known to not always work properly in all circumstances. If it fails for you, then best is to manually gather and set the cookie headers. You basically need to grab all Set-Cookie headers from the response of the login or the first GET request and then pass this through the subsequent requests.
// Gather all cookies on the first request.
URLConnection connection = new URL(url).openConnection();
List<String> cookies = connection.getHeaderFields().get("Set-Cookie");
// ...
// Then use the same cookies on all subsequent requests.
connection = new URL(url).openConnection();
for (String cookie : cookies) {
connection.addRequestProperty("Cookie", cookie.split(";", 2)[0]);
}
// ...
The split(";", 2)[0] is there to get rid of cookie attributes which are irrelevant for the server side like expires, path, etc. Alternatively, you could also use cookie.substring(0, cookie.indexOf(';')) instead of split().
Streaming mode
The HttpURLConnection will by default buffer the entire request body before actually sending it, regardless of whether you've set a fixed content length yourself using connection.setRequestProperty("Content-Length", contentLength);. This may cause OutOfMemoryExceptions whenever you concurrently send large POST requests (e.g. uploading files). To avoid this, you would like to set the HttpURLConnection#setFixedLengthStreamingMode().
httpConnection.setFixedLengthStreamingMode(contentLength);
But if the content length is really not known beforehand, then you can make use of chunked streaming mode by setting the HttpURLConnection#setChunkedStreamingMode() accordingly. This will set the HTTP Transfer-Encoding header to chunked which will force the request body being sent in chunks. The below example will send the body in chunks of 1 KB.
httpConnection.setChunkedStreamingMode(1024);
User-Agent
It can happen that a request returns an unexpected response, while it works fine with a real web browser. The server side is probably blocking requests based on the User-Agent request header. The URLConnection will by default set it to Java/1.6.0_19 where the last part is obviously the JRE version. You can override this as follows:
connection.setRequestProperty("User-Agent", "Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/41.0.2228.0 Safari/537.36"); // Do as if you're using Chrome 41 on Windows 7.
Use the User-Agent string from a recent browser.
Error handling
If the HTTP response code is 4nn (Client Error) or 5nn (Server Error), then you may want to read the HttpURLConnection#getErrorStream() to see if the server has sent any useful error information.
InputStream error = ((HttpURLConnection) connection).getErrorStream();
If the HTTP response code is -1, then something went wrong with connection and response handling. The HttpURLConnection implementation is in older JREs somewhat buggy with keeping connections alive. You may want to turn it off by setting the http.keepAlive system property to false. You can do this programmatically in the beginning of your application by:
System.setProperty("http.keepAlive", "false");
Uploading files
You'd normally use multipart/form-data encoding for mixed POST content (binary and character data). The encoding is in more detail described in RFC2388.
String param = "value";
File textFile = new File("/path/to/file.txt");
File binaryFile = new File("/path/to/file.bin");
String boundary = Long.toHexString(System.currentTimeMillis()); // Just generate some unique random value.
String CRLF = "\r\n"; // Line separator required by multipart/form-data.
URLConnection connection = new URL(url).openConnection();
connection.setDoOutput(true);
connection.setRequestProperty("Content-Type", "multipart/form-data; boundary=" + boundary);
try (
OutputStream output = connection.getOutputStream();
PrintWriter writer = new PrintWriter(new OutputStreamWriter(output, charset), true);
) {
// Send normal param.
writer.append("--" + boundary).append(CRLF);
writer.append("Content-Disposition: form-data; name=\"param\"").append(CRLF);
writer.append("Content-Type: text/plain; charset=" + charset).append(CRLF);
writer.append(CRLF).append(param).append(CRLF).flush();
// Send text file.
writer.append("--" + boundary).append(CRLF);
writer.append("Content-Disposition: form-data; name=\"textFile\"; filename=\"" + textFile.getName() + "\"").append(CRLF);
writer.append("Content-Type: text/plain; charset=" + charset).append(CRLF); // Text file itself must be saved in this charset!
writer.append(CRLF).flush();
Files.copy(textFile.toPath(), output);
output.flush(); // Important before continuing with writer!
writer.append(CRLF).flush(); // CRLF is important! It indicates end of boundary.
// Send binary file.
writer.append("--" + boundary).append(CRLF);
writer.append("Content-Disposition: form-data; name=\"binaryFile\"; filename=\"" + binaryFile.getName() + "\"").append(CRLF);
writer.append("Content-Type: " + URLConnection.guessContentTypeFromName(binaryFile.getName())).append(CRLF);
writer.append("Content-Transfer-Encoding: binary").append(CRLF);
writer.append(CRLF).flush();
Files.copy(binaryFile.toPath(), output);
output.flush(); // Important before continuing with writer!
writer.append(CRLF).flush(); // CRLF is important! It indicates end of boundary.
// End of multipart/form-data.
writer.append("--" + boundary + "--").append(CRLF).flush();
}
If the other side is an HttpServlet, then its doPost() method will be called and the parts will be available by HttpServletRequest#getPart() (note, thus not getParameter() and so on!). The getPart() method is however relatively new, it's introduced in Servlet 3.0 (Glassfish 3, Tomcat 7, etc.). Prior to Servlet 3.0, your best choice is using Apache Commons FileUpload to parse a multipart/form-data request. Also see this answer for examples of both the FileUpload and the Servelt 3.0 approaches.
Dealing with untrusted or misconfigured HTTPS sites
In case you're developing for Android instead of Java, be careful: the workaround below may save your day if you don't have correct certificates deployed during development. But you should not use it for production. These days (April 2021) Google will not allow your app be distributed on Play Store if they detect insecure hostname verifier, see https://support.google.com/faqs/answer/7188426.
Sometimes you need to connect an HTTPS URL, perhaps because you're writing a web scraper. In that case, you may likely face a javax.net.ssl.SSLException: Not trusted server certificate on some HTTPS sites who doesn't keep their SSL certificates up to date, or a java.security.cert.CertificateException: No subject alternative DNS name matching [hostname] found or javax.net.ssl.SSLProtocolException: handshake alert: unrecognized_name on some misconfigured HTTPS sites.
The following one-time-run static initializer in your web scraper class should make HttpsURLConnection more lenient as to those HTTPS sites and thus not throw those exceptions anymore.
static {
TrustManager[] trustAllCertificates = new TrustManager[] {
new X509TrustManager() {
@Override
public X509Certificate[] getAcceptedIssuers() {
return null; // Not relevant.
}
@Override
public void checkClientTrusted(X509Certificate[] certs, String authType) {
// Do nothing. Just allow them all.
}
@Override
public void checkServerTrusted(X509Certificate[] certs, String authType) {
// Do nothing. Just allow them all.
}
}
};
HostnameVerifier trustAllHostnames = new HostnameVerifier() {
@Override
public boolean verify(String hostname, SSLSession session) {
return true; // Just allow them all.
}
};
try {
System.setProperty("jsse.enableSNIExtension", "false");
SSLContext sc = SSLContext.getInstance("SSL");
sc.init(null, trustAllCertificates, new SecureRandom());
HttpsURLConnection.setDefaultSSLSocketFactory(sc.getSocketFactory());
HttpsURLConnection.setDefaultHostnameVerifier(trustAllHostnames);
}
catch (GeneralSecurityException e) {
throw new ExceptionInInitializerError(e);
}
}
Last words
The Apache HttpComponents HttpClient is much more convenient in this all :)
Parsing and extracting HTML
If all you want is parsing and extracting data from HTML, then better use a HTML parser like Jsoup.
Best Answer
In the end, contrary to my initial tests, web.xml solution worked for me on Tomcat 7.
E.g. I added this snippet to web.xml and it marks session cookie as secure even when reverse proxy contacts tomcat over plain HTTP.