Disadvantages of dynamic arrays
- May cause a large waste of memory space.
Singly linked list
- Linked lists are a kind of
Chain storeThe memory addresses of all elements are not necessarily contiguous.
Design of linked lists
- First of all, there’s a
size: Records the number of elements - Second, have a
NodeObject containing references to Element and next - The linked list class should have one
first(head)The reference.
Interface design for linked lists
The clear() operation of the linked list
- Just set the first reference to
null - When the first element is released, the
nextThe other elements are then released.
Add elements
- You need to point the pointer to next of the new element to the prev.next element, and then prev.next to the new element
- Check whether it is the first node
- We can add a virtual head node to unify all operations.
Remove elements
- Prev.next points directly to the next element that you want to delete
public class LinkedList<E> extends AbstractList<E> {
/** * the first element reference */
private Node<E> first;
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) {
returni; } node = node.next; }}else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (element.equals(node.element)) {
returni; } node = node.next; }}return -1;
}
@Override
public boolean contains(E element) {
return false;
}
@Override
public E get(int index) {
return node(index).element;
}
/** * sets the new value at the specified location. The node object does not need to be changed@param index
* @param element
* @return* /
public E set(int index, E element) {
Node<E> node = node(index);
E oldValue = node.element;
node.element = element;
return oldValue;
}
@Override
public void add(E element) {
add(size, element);
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
// Special processing if index is 0
if (index == 0) {
first = new Node<>(element, first);
} else {
// Next for prev becomes next for new node
// Next of prex points to the new node
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> delNode = first;
if (index == 0) {
first = first.next;
} else {
Node<E> prev = node(index - 1);
delNode = prev.next;
prev.next = delNode.next;
}
return delNode.element;
}
@Override
public void clear(a) {
first = null;
size = 0;
}
/** * get the node object ** corresponding to the index position@param index
* @return* /
private Node<E> node(int index) {
rangeCheck(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
@Override
public String toString(a) {
StringBuilder sb = new StringBuilder();
sb.append("[");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if(i ! =0) {
sb.append(",");
}
sb.append(node.element.toString());
node = node.next;
}
sb.append("]");
return sb.toString();
}
/** * Node object **@param <E>
*/
private static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next; }}}Copy the codeTwo-way linked list
Implementation of bidirectional linked list
public class LinkedList<E> extends AbstractList<E> {
private Node<E> first;
private Node<E> last;
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
rangeCheck(index);
Node<E> node = node(index);
E oldValue = node.element;
node.element = element;
return oldValue;
}
@Override
public void add(E element) {
add(size, element);
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
// Insert either the last element or the first element
if (index == size) {
// From the perspective of the last element
Node<E> oldLast = last;
last = new Node<>(element, oldLast, null);
if (oldLast == null) {
first = last;
} else{ oldLast.next = last; }}else {
// Insert the next node of the node
Node<E> next = node(index);
// Insert the last node of the node
Node<E> prev = next.prev;
/ / the new node
Node<E> newNode = new Node<E>(element, prev, next);
next.prev = newNode;
if (prev == null) { // index = 0
first = newNode;
} else {
prev.next = newNode;
}
}
size++;
}
@Override
public E remove(int index) {
rangeCheck(index);
Node<E> delNode = node(index);
Node<E> next = delNode.next;
Node<E> prev = delNode.prev;
// Delete the first element
if (prev == null) {
first = next;
} else {
prev.next = next;
}
// Remove the last element
if (next == null) {
last = prev;
} else {
next.prev = prev;
}
size--;
return delNode.element;
}
@Override
public int indexOf(E element) {
Node<E> node = first;
if (element == null) {
for (int i = 0; i < size; i++) {
if (node.element == null)
returni; node = node.next; }}else {
for (int i = 0; i < size; i++) {
if (element.equals(node.element))
returni; node = node.next; }}return -1;
}
@Override
public void clear(a) {
// Not referenced by the GC root object is automatically released
first = null;
last = null;
size = 0;
}
/** * find element ** by index@param index
* @return* /
private Node<E> node(int index) {
// java.util.LinkedList
// asert index
Node<E> node = null;
// Look left
if (index < (size >> 1)) {
node = last;
for (int i = 0; i < index; i++) { node = node.next; }}else {
// Start the search
node = last;
for (int i = size - 1; i > index; i--) { node = node.prev; }}return node;
}
private static class Node<E> {
E element;
Node<E> prev;
Node<E> next;
public Node(E element, Node<E> prev, Node<E> next) {
this.element = element;
this.next = next;
this.prev = prev; }}}Copy the code