How do I implement a simple LinkedList in Java

Both LinkedList and ArrayList are concrete implementation classes of the List interface. In terms of function, LinkedList and ArrayList are roughly 1, but because they are implemented in different ways, their efficiency is different when performing the same operation.

For abstract data structures-linear tables, there are two kinds of linear tables: one is a sequential table that stores the structure sequentially, and the other is a linked list that describes its logical location by a pointer.

Specific to the Java implementation:

The sequential storage table is implemented with arrays, and List formed by encapsulating various operations based on arrays is ArrayList Linked list is a pointer to describe its logical position. In Java, List formed by encapsulating various operations based on bidirectional linked list is LinkedList

For the insertion and deletion operation, for each element inserted by ArrayList, we first need to determine whether the space of the array is enough or not. On the basis of sufficient space, we insert the element at the specified index position, but the index and subsequent elements should be moved back. While the delete operation does not need to determine whether the space is sufficient, it also requires the index and later elements to move forward, which adds time complexity. This is not the case for LinkedList, which USES Pointers to indicate its logical location, so both inserts and deletes have a time complexity of ** O(1) **

Although insertion and deletion time is very high for ArrayList, the operation of finding the element in the specified location is very fast because the element corresponding to the subscript can be obtained directly from the array. On the contrary, LinkedList cannot directly return the element in the specified location. It requires 1 query, whose time complexity is ** O(n) **

And how to achieve Java ArrayList classic entity class 1, the purpose of the implementation is mainly to practice and master the principle of the official implementation and 1 some skills, so many need to cooperate with other classes of methods and functions, such as iterator is not implemented here

Therefore, LinkedList is implemented as follows:

add method

get method

indexOf method

remove method

Like the name of the implementation ArrayList, it is SimpleLinkedList. Source address, welcome star,fork

Construct a bidirectional linked list

The code to build is as follows:

 private static class Node<E>{
 E item;
 Node<E> next;
 Node<E> prev;
 public Node(E item, Node<E> next, Node<E> prev) {
 this.item = item;
 this.next = next;
 this.prev = prev;
 }
 } 

Conventional bidirectional linked list construction method, 1 number field holds array, 1 before pointer to 1 Node type element, 1 after pointer to 1 Node type element.

For the implementation of LinkedList, the following three member variables are required

 private int size;
 private Node<E> first;
 private Node<E> last;

Add method

add method implemented here is simple add(E e) and add(int index,E e) two methods, addAll() other set conversion LinkedList method, temporarily put to achieve later.

The add method has two overloaded methods that correspond to different ways of adding them. First, the realization of add(E e) method.

 public boolean add(E element) {
 addAtLast(element);
 return true;
 }

Adding an element without specifying a location is added to the end of the list by default. The core code for addAtLast is as follows:

 private void addAtLast(E element) {
 Node<E> l = last;
 Node<E> node = new Node<E>(element, null, l);
 last = node;
 if (l == null) {
 first = node;
 } else {
 l.next = node;
 }
 size++;
 }

First find the last bit of Node element, then create a new Node element based on element, where next points to null and prev points to the last bit of Node. After the Node element is created, last becomes the first Node element created, and then you simply add the new node element to the list. That is, let the l object (the last bit, now the next pointer to the second-to-last element, points to the new node element). So far, next of the new node element points to null,prev points to the penultimate element, and next of the penultimate element points to the new node, and node is successfully added to the list.

As can be seen from the above operation, the insertion operation is very time saving, and the expansion and moving elements are much faster than the ArrayList.

add's second overload method add(int index,E e), first look at the code implementation:

 public void add(int index, E element) {
 checkRangeForAdd(index);
 if (index == size) {
 addAtLast(element);
 } else {
 Node<E> l = node(index);
 addBeforeNode(element, l);
 }
 }

First determine if the index to be inserted is within the scope, and if so, then perform subsequent add operations. If the index to be inserted happens to be the last bit, then addAtLast as described above is executed. If not, the corresponding Node element of index is obtained, and addBeforeNode is executed.

Get the Node element corresponding to index, which is the node method, the code is as follows:

 private Node<E> node(int index) {
 if (index < (size << 1)) {
 Node<E> cursor = first;
 for (int i = 0; i < index; i++) {
 cursor = cursor.next;
 }
 return cursor;
 } else {
 Node<E> cursor = last;
 for (int i = size - 1; i > index; i--) {
 cursor = cursor.prev;
 }
 return cursor;
 }
 }

The search here USES 2 minutes to find, save search time, but also applied to the bidirectional linked list characteristics. First, index is in the first half of the range, or the second half of the range. If it is the first half, the cursor Node is initially first, and the cursor next of Node element is used to point to the element where index is located. If it is the second half, the cursor Node is initially last, and the prev of the Node element is used to point to the element where index is located.

addBeforeNode inserts the new node before the specified element as follows:

 private void addBeforeNode(E element, Node<E> specifiedNode) {
 Node<E> preNode = specifiedNode.prev;
 Node<E> newNode = new Node<>(element, specifiedNode, preNode);
 if (preNode == null) {
 first = newNode;
 } else {
 preNode.next = newNode;
 }
 specifiedNode.prev = newNode;
 size++;
 }

The insertion is simple: the prev of the new node is the prev of the original index element, and the next of the new node is the original index element. All that remains is to place the node into the linked list, making the next of the original index element the new node, but to determine whether preNode is empty, if yes, that means newNode is the first element, which is first.

At this point, the add method is complete.

get method

The get method is very simple with the node method described above. The code is as follows:

 public E get(int index) {
 checkRange(index);
 return node(index).item;
 }

checkRange checks to see if index is not in scope.

 private void checkRange(int index) {
 if (index >= size || index < 0) {
 throw new IndexOutOfBoundsException(" The specified index More than limit ");
 }
 }

indexOf method

indexOf(Object o) is used to obtain the subscript of the specified element.

 public int indexOf(Object element) {
 Node<E> cursor = first;
 int count = 0;
 while (cursor != null) {
 if (element != null) {
 if (element.equals(cursor.item)) {
  return count;
 }
 }else{
 if (cursor.item == null) {
  return count;
 }
 }
 count ++;
 cursor = cursor.next;
 }
 return -1;
 }

Like ArrayList1, it starts from the first bit to determine whether element is null or not. It is divided into two cases.

remove method

remove method is the same as add method 1. There are also two overloaded methods, remove(Object o) and remove(int index)

First look at the simple remove(int index) method, the code is as follows:

 private int size;
 private Node<E> first;
 private Node<E> last;

0

deleteLink is a method to delete the link of the node corresponding to this index. Its code is as follows:

 private int size;
 private Node<E> first;
 private Node<E> last;

1

First, the Node element corresponding to the index element is obtained, and the first and last element of the Node element are obtained. Next, you only need to connect the first element directly to the last element, and the rest just need to determine whether the first element and the last element are null. Only the first element is manipulated to determine whether the first element is null, and only the last element is manipulated to determine whether the last element is null. Finally, each reference to the element to be removed is null.

remove another overloaded method, remove(Object o), is very simple after implementing the indexOf and deleteLink methods.

 private int size;
 private Node<E> first;
 private Node<E> last;

2

Gets the subscript for that element, and executes the deleteLink method to complete the remove operation.

conclusion

So far, a simple function of LinkedList is completed, all the code can see the source address,