First look and then like, give yourself a little time to think, wechat search [Silent King 2] focus on this talented programmer. This article has been collected at GitHub github.com/itwanger, along with interview questions compiled by top companies, and my series of articles.
The last one into the pit of ArrayList, small friends have good response, then this one will continue to pit LinkedList, it is two close brothers, love each other to kill the kind of, never abandon the kind of, introduced this must introduce that kind of.
To tell you a piece of good news, I wrote a Java manual of more than 40,000 words, friends can reply “Xiao Bai” in the background of “Silent King ii” public account to get a free download link. If you feel good about it, please forward it to your friends who need it.
When I first started learning Java, I was wondering why I need a LinkedList when there is an ArrayList. I was so naive, I didn’t know if there were any friends with the same style. I don’t know the difference between ArrayList and LinkedList. So this article can kick that naivete away.
Like an array, LinkedList is a linear data structure, but rather than storing elements in contiguous locations like an array, it is linked to each other by reference.
Each element in the LinkedList is called a Node, and each Node contains three items: the element itself, the reference address to the next element, and the reference address to the previous element.
Node is a private static inner class of the LinkedList class, with the source code as follows:
private static class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Copy the codeLinkedList looks something like this:
-
The first node has no previous node, so prev is null;
-
The last node is null because there is no next node.
-
This is a bidirectional linked list, where each node is made up of three parts, front and back nodes and values.
Some of you may be wondering, like me, “Why design a LinkedList?” It would be nice to call the author of the LinkedList class, but they don’t have contact information. Unfortunately, I have to explain it to you.
First, the size of an array is fixed, and even if an ArrayList can be automatically expanded, there are limitations: if the declared size is insufficient, it needs to be expanded. If the size of the declaration is much larger than the actual number of elements, memory will be wasted. Even though the algorithms are pretty elegant, even though there’s more than enough memory.
Second, the elements of an array require contiguous memory locations to store their values. This is the real reason arrayLists are expensive when deleting or inserting elements, because we have to move certain elements to make room for new ones, such as:
Now you have an array, 10, 12, 15, 20, 4, 5, 100, and if you want to insert an element of 99 at 12, you have to move the element after 12 back to make room for 99.
The same is true for deletes; all deleted elements must be moved forward once.
LinkedList is free of this restriction:
First, LinkedList allows memory to be allocated dynamically, which means that memory allocation is done by the compiler at runtime and we do not need to specify the size at LinkedList declaration time.
Second, LinkedList does not need to store elements in contiguous locations, because nodes can specify either the next node or the previous node by reference. That is, the LinkedList is cheap to insert and delete because there is no need to move other elements, just update the reference addresses of the previous node and the one after it.
The hierarchy of the LinkedList class is shown below:
-
LinkedList is a bidirectional LinkedList derived from AbstractSequentialList, so it can also operate as a stack, queue, or double-endian queue.
-
LinkedList implements the List interface, so it can be queued.
-
LinkedList implements the Deque interface, so it can be used as a two-ended queue.
With some theory behind LinkedList, let’s take a look at how to use it.
How do I create a LinkedList
LinkedList<String> list = new LinkedList<>();
Copy the codeAs with ArrayList, you can create a LinkedList of type string using the above statement (Angle brackets qualify the types of elements in the LinkedList, and attempts to add other types of elements will result in a compilation error).
However, LinkedList cannot be sized when created, as ArrayList can.
02. Add an element to the LinkedList
You can add an element to the LinkedList using the add() method:
LinkedList<String> list = new LinkedList<>();
list.add("Silent King II.");
list.add("Silent King three.");
list.add("The Silent King iv.");
Copy the codeIf you’re interested, check out the source code for the add() method, which calls linkLast() when adding elements.
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Copy the codeWhen the first element is added, last is null, new nodes are created (next and prev are both null), and new nodes are assigned to last and first. When the second element is added, last is the first node, a new node is created (next is null, prev is the first node), and last is updated to the new node, first remains unchanged, and next of the first node is updated to the second node. And so on.
You can also add elements to the first by using the addFirst() method; The addLast() method adds the element to the end; The add(int index, E Element) method adds an element to the specified location.
Update the LinkedList
You can use the set() method to change elements in the LinkedList, providing subscripts and new elements.
list.set(0."The Silent Five.");
Copy the codeSet () = set();
public E set(int index, E element) {
checkElementIndex(index);
LinkedList.Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
Copy the codeThis method checks the specified subscript to see if it is out of bounds, and then looks for nodes based on the subscript:
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Copy the codeThe node() method makes a preliminary determination of the index, and if it is near the end, start at the end. This saves a lot of traversal time.
When the node is found, the new value is replaced and the old value is returned.
Delete the LinkedList element
You can remove elements at the specified position by using the remove() method:
list.remove(1);
Copy the codeThis method calls the unlink() method to update the front and back nodes.
E unlink(LinkedList.Node<E> x) {
// assert x ! = null;
final E element = x.item;
final LinkedList.Node<E> next = x.next;
final LinkedList.Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeYou can also remove the first and last node using the removeFirst() and removeLast() methods.
Find elements in the LinkedList
To find an element in positive order, use the indexOf() method; If you want to find an element in reverse order, you can use the lastIndexOf() method.
IndexOf () = indexOf();
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for(LinkedList.Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for(LinkedList.Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
Copy the codeIf the element to be searched is null, use the “==” operator to avoid throwing a null pointer exception. Otherwise, use the equals() method for comparison.
In addition, the getFirst() method is used to get the first element; The getLast() method is used to get the last element; The poll() and pollFirst() methods are used to delete and return the first element (the body of the method is identical despite the names); The pollLast() method is used to delete and return the last element; The peekFirst() method is used to return but not delete the first element.
6, the last
If we want to achieve a linked list of words, the above increase, delete, change and check the wheel method is certain to white piao, wrong, must learn from ah.
As mentioned in the previous ArrayList article, the time complexity of randomly accessing an element is O(1), but LinkedList is more complicated because the time complexity increases by as much as the data increases, and the time complexity is O(n) because it is iterated.
Whether LinkedList can insert, add, and delete elements faster than ArrayList depends on the size of the data and where the elements are located. In theory, however, since you don’t need to move the array, it should be faster. But we’ll find out in the next article.
I am the Silent King 2, a programmer with good looks but mediocre talent. Attention can improve learning efficiency, don’t forget three even ah, like, favorites, leave a message, I don’t pick, Ollie.
Note: If there are any problems with the article, please kindly correct them.
If you feel the article to you some help welcome wechat search “silent king ii” first time to read, reply to “small white” more have my liver 40,000 + words Java small white manual 2.0 version, this article GitHub github.com/itwanger has included, welcome star.