ArrayList and LinkedList are succinctly compared:
ArrayList has fast query speed and slow insertion (insert in the middle, not at the end), while LinkedList has slow query speed and fast insertion (insert in the middle). What is the reason for their difference? After understanding their underlying implementation, we can know that the underlying of ArrayList is implemented by array. Array is to apply for a continuous memory in memory and then read and write data in it. The query time complexity is O(1). However, if you want to add or delete data into the array, the number behind the add (delete) position should be in the corresponding position forward or backward, Therefore, the time complexity of its addition and deletion is O(n). However, the underlying layer of LinkedList is realized by linked list, and the time complexity of linked list query data is O(n), while the time complexity of adding and deleting data is O(1). It can be seen that they have different differences in the two dimensions of query and data addition and deletion, so you can choose different data structures according to your own needs.
If you simply put it in, then take it out and use ArrayList, it will be more efficient!
//Declaration of LinkedList class in source code
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{Source code comments:
(1) LinkedList implements both interface List and Deque(LinkedList implements all methods of these two interfaces). It is both a linked List and a double ended queue. It allows you to add any element, including null elements.
(2) the implementation of all methods of LinkedList reflects the characteristics of double linked list. All operations related to index are automatically traversed from the beginning or end of LinkedList (if the index is closer to the beginning, it is automatically traversed from the beginning, and closer to the end, it is automatically traversed from the end).
(3) LinkedList is not thread safe. If structure modification is involved in multi-threaded environment (structure modification refers to adding or deleting one or more elements), thread safety of LinkedList must be guaranteed externally (by synchronizing the objects holding LinkedList). If there is no object holding LinkedList, the method synchronizedList(new LinkedList(...)) of class Collections should be used. The specific code is as follows:
List list = Collections.synchronizedList(new LinkedList(...));
It's best to do this when creating LinkedList objects to prevent any unsafe operations.
(4) after obtaining the iterator or list iterator, unless the LinkedList structure is modified by using the methods provided by them (methods remove() and add()), the ConcurrentModificationException (quick failure mechanism) will be thrown. The iterator will not risk any uncertain behavior in the uncertain time in the future (if the structure of LinkedList is modified during the iteration of multi-threaded environment, many results may be returned).
(5) note that there is no guarantee that the fast failure mechanism will be executed. It can only be said that the iterator will try its best to throw the ConcurrentModificationException exception. Therefore, it is wrong to ensure the correctness of the program through the rapid failure mechanism, which can only be used to detect errors.
Figure displaying the node:
Each node in the LinkedList is a separate storage space. "Element" is stored in the node, but there are not only elements in the node. The bottom layer of ArrayList is array, which is a continuous storage space (accessed by holding the reference of array + "[index]" +), so each storage space only needs to store elements and does not need to store the relationship between them. The underlying layer of the LinkedList is a linked list (bidirectional), which is not a continuous storage space, so each storage space (node) needs to store not only elements, but also the relationship between them (prev: the location of the previous node, if any. Next: the location of the next node, if any).
Illustration of linked list:
In the linked list, an independent storage space is a Node. At the same time, a Node is an object instance of an internal class Node. The linked list is composed of several nodes,
Source code of internal Node class:
//Type of linked list node
//An object corresponds to a node
private static class Node<E> {
//Reference to element
//If it is null, it means that no element is stored. If it is not null, it means that some type of element is stored
E item;
//Reference to the next node
//The reference represents the hexadecimal address value of the object, so it can also be annotated as the address of the next node in memory
//If it is null, it may be an empty linked list or a tail node
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
//Element reference initialization
this.item = element;
//Reference initialization of previous node
this.next = next;
//Reference initialization of the next node
this.prev = prev;
}
}
Variable
size
//Number of elements, initialized to 0 //The keyword transient indicates that it cannot be serialized transient int size = 0;
first
//Fixed reference of the first node (to facilitate the creation and addition of nodes and the search and traversal of linked lists) //The linked list must create and add the first node before it can create and add the second node, and so on //Search traversal is the same. A linked list is a sequential access list, which can only be accessed one by one from the beginning or end //Therefore, the first node cannot be anonymous, and a fixed reference is needed to facilitate subsequent use //The keyword transient indicates that it cannot be serialized transient Node<E> first;
last
//Fixed reference of tail node (convenient for node search and traversal) //The keyword transient indicates that it cannot be serialized transient Node<E> last;
constructor
LinkedList()
//Construct a method to create an empty LinkedList without any nodes
public LinkedList() {}LinkedList(Collection<? extends E> c)
//Construct a method to create such a LinkedList
//① The number of nodes is consistent with the number of elements in the specified set c
//② . each element in the specified set c is stored in the node corresponding to the index value
//In other words, the order of nodes is exactly the same as that of the elements of the specified set c
public LinkedList(Collection<? extends E> c) {
//Call the parameterless constructor if it's in later Java
//Changes in the upgraded version can be consistent with it in real time
//It ensures the scalability of the program and facilitates the later code maintenance
this();
//Through the method addall (collection <? Extensions E > C)
//Add all elements of c
addAll(c);
}
linkFirst(E e)
//Create a new node containing element e
//And link to the linkfirst, which is the new first node of the linked list
//The meaning of the method: LinkedList implement s the interfaces Queue and Deque at the same time
private void linkFirst(E e) {
//Assuming that the linked list is not empty, obtain and pass the reference of the first node
//After passing, the reference f and first point to the first node at the same time
//This step is actually copying the reference of the first node
final Node<E> f = first;
//Provide the following parameters to create a node object newNode:
//① . the reference of the previous node is null
//② Element e
//③ . reference of the next node f
//newNode is actually a new first node for two reasons:
//① In the linked list, only the previous node reference of the first node is null
//② . the original first node f becomes the next node of newNode
//③ The maintenance of node relationship is put in the constructor (refer to the screenshot)
final Node<E> newNode = new Node<>(null, e, f);
//Assign newNode to first to ensure that first is always the reference of the first node
first = newNode;
//The above code only initializes first, not last
//If the first node f is null, the linked list is empty
//Therefore, the newly created node newNode is both the first node and the tail node
if (f == null)
//Initialize last
last = newNode;
else
//If the first node f is not empty
//Two aspects need to be considered: elements and relationships
//The element is added by the client programmer
//Just consider the relationship here
//The prev of the first node f must be null
//Now a new first node newNode is created
//f is naturally the second node
//Therefore, it needs to be expressed by code:
//The last node of f is newNode
//So as to ensure the correct relationship of each node
f.prev = newNode;
//Add a node, length + 1
size++;
//It inherits from the abstract class AbstractList to ensure the normal implementation of the fast failure mechanism
//The new node is a structural modification
modCount++;
}
linkLast(E e)
//Create a new node containing element e and link it to the end of the linked list (linkLast)
//This node is the new tail node of the linked list
//The meaning of the method: LinkedList implement s the interfaces Queue and Deque at the same time
//Their methods can effectively avoid code duplication
void linkLast(E e) {
//Assuming that the linked list is not empty, obtain and pass the reference of the tail node
//After passing, the reference l and last point to the tail node at the same time
//This step is actually copying the reference of the tail node
final Node<E> l = last;
//Create a node object newNode: / / ①, the reference of the previous node l ②, and element e
//③ . the reference of the next node is null
//newNode is actually a new tail node for two reasons:
//① In the linked list, only the next node reference of the tail node is null
//② . the original tail node l becomes the previous node of newNode
final Node<E> newNode = new Node<>(l, e, null);
//Assign newNode to last to ensure that last is always a reference to the tail node
last = newNode;
//The above code only initializes last, not first
//If the tail node l is null, the linked list is empty
//Therefore, the newly created node newNode is both the tail node and the first node
if (l == null)
//Initialize first
first = newNode;
else
//If the tail node l is not empty
//Two aspects need to be considered: elements and relationships
//The element is added by the client programmer
//Just consider the relationship here
//The next of tail node l must be null
//Now a new tail node newNode is created
//l naturally, it is the penultimate node
//Therefore, it needs to be expressed by code:
//The next node of l is newNode
//So as to ensure the correct relationship of each node
l.next = newNode;
//Add a node, length + 1
size++;
//It inherits from the abstract class AbstractList to ensure the normal implementation of the fast failure mechanism
modCount++;
}
linkBefore(E e, Node< E > succ)
//Creates a node containing the specified element e
//And link it before the specified node succ (linkBefore)
void linkBefore(E e, Node<E> succ) {
//Gets the previous node of node succ
final Node<E> pred = succ.prev;
//Provide the following parameters to create a node object newNode:
//① . reference pred of previous node
//② Element e
//③ . reference succ of the next node
final Node<E> newNode = new Node<>(pred, e, succ);
//After creation, you also need to maintain the relationship between nodes
//To ensure that the newNode is the last node of succ
succ.prev = newNode;
//---------------Some other situations need to be considered below
//If pred is null, succ is the first node of the linked list
//(only the previous node of the first node is null)
//Since it is the first node, there is another fixed reference first
if (pred == null)
//newNode replaces succ as the new first node
//First needs to be reinitialized to ensure that first is always the reference of the first node
first = newNode;
//If pred is not null
//The above code only maintains the relationship between newNode → succ direction
//(succ.prev = newNode)
//LinkedList is bidirectional
//Therefore, it is also necessary to maintain the relationship between pred → newNode direction
else
//newNode is the next node of pred
pred.next = newNode;
//Add a node, length + 1
size++;
//It inherits from the abstract class AbstractList to ensure the normal implementation of the fast failure mechanism
//The new node is a structural modification
modCount++;
}
unlinkFirst(Node< E > f)
//Divide the linked list into two at the specified node f
//Directly discard the left side of the linked list (including node f)
//On the right of the linked list is a new linked list
private E unlinkFirst(Node<E> f) {
//Get the element of node f
final E element = f.item;
//Get the next node of node f
final Node<E> next = f.next;
//Empty elements of node f
f.item = null;
//Disconnect node f from the next node
//Divide the list into two here
//Directly discard the left side of the linked list (including node f)
f.next = null;
//The first node on the right of the linked list
//That is, the next node of node f
//Become the first node of the new linked list
//first needs to be reinitialized
//Ensure that first is always the reference of the first node
first = next;
//---------------Some other situations need to be considered below
//If next is null, the new linked list is null
if (next == null)
//Then the tail node of the new linked list is also null
//last needs to be reinitialized
last = null;
//If next is not null, it is the first node of the new linked list
//The above code only breaks the relationship between the f → next direction
//(f.next = null)
//LinkedList is bidirectional
//Therefore, it is also necessary to disconnect the relationship between the next → f direction
else
next.prev = null;
//The first node should also be null
//Delete a node, length - 1
size--;
//It inherits from the abstract class AbstractList to ensure the normal implementation of the fast failure mechanism
//Deleting a node is a structural modification
modCount++;
return element;
}
unlinkLast(Node< E > l)
//Divide the linked list into two at the specified node l
//Drop directly on the right side of the linked list (including node l)
//On the left of the linked list is a new linked list
private E unlinkLast(Node<E> l) {
//Get element of node l
final E element = l.item;
//Gets the previous node of node l
final Node<E> prev = l.prev;
//Empty elements of node l
l.item = null;
//Disconnect node l from the previous node
//Here, the linked list is divided into two
//Drop directly on the right side of the linked list (including node l)
l.prev = null;
//Tail node on the left of the linked list
//That is, prev, the previous node of node l
//Become the tail node of the new linked list
//last needs to be reinitialized
//Ensure that last is always a reference to the tail node
last = prev;
//---------------Some other situations need to be considered below
//If prev is null, the new linked list is null
if (prev == null)
//Then the first node of the new linked list is also null
//first needs to be reinitialized
first = null;
//If prev is not null, it is the tail node of the new linked list
//The above code only breaks the relationship between l → prev direction
//(l.prev = null)
//LinkedList is bidirectional
//Therefore, it is also necessary to disconnect the relationship between prev → l direction
else
prev.next = null;
//At the same time, the next node of the tail node should also be null
//Delete a node, length - 1
size--;
//It inherits from the abstract class AbstractList to ensure the normal implementation of the fast failure mechanism
//Deleting a node is a structural modification
modCount++;
return element;
}
unlink(Node< E > x)
//Delete specified node x
E unlink(Node<E> x) {
//Gets the element of node x
final E element = x.item;
//Gets the next node of node x
final Node<E> next = x.next;
//Gets the previous node of node x
final Node<E> prev = x.prev;
//If prev is null, x is the first node
//After deleting x, its next node will automatically become the new first node
if (prev == null) {
//First needs to be reinitialized to ensure that first is always the reference of the first node
first = next;
} else {
prev.next = next;
x.prev = null;
}
//If next is null, x is the tail node
//After deleting x, its previous node (next) will automatically become a new tail node
if (next == null) {
//Last needs to be reinitialized to ensure that last is always a reference to the tail node
last = prev;
//If next is not null, you only need to maintain the relationship between nodes
//Delete x, then its next node (next.prev)
//And the previous node (prev) will be directly connected
} else {
next.prev = prev;
//linkedList is bidirectional
//The above code only breaks the relationship between the x → prev direction
//You also need to break the relationship in the x → next direction
x.next = null;
}
//Empty element of node x
x.item = null;
//Delete a node, length - 1
size--;
//It inherits from the abstract class AbstractList to ensure the normal implementation of the fast failure mechanism
//Deleting a node is a structural modification
modCount++;
return element;
}
The above are the internal support methods of LinkedList. The methods provided by LinkedList will be introduced below, including the following categories: methods of interface Deque, methods of interface Queue, methods of stack, etc.
Deque interface method (double ended queue)
Deque's feature is that nodes can be added and deleted both at the head and at the tail.
getFirst()
//Returns the element of the first node
public E getFirst() {
//Get first node
final Node<E> f = first;
//If the first node is null
if (f == null)
//Throw NoSuchElementException exception
throw new NoSuchElementException();
//Returns the element of the first node
return f.item;
}
getLast()
//Returns the element of the tail node
public E getLast() {
//Get tail node
final Node<E> l = last;
//If the tail node is null
if (l == null)
//Throw NoSuchElementException exception
throw new NoSuchElementException();
//Returns the element of the tail node
return l.item;
}
removeFirst()
//Delete a node from the head of the linked list
public E removeFirst() {
//Get first node
final Node<E> f = first;
//If the first node is null
if (f == null)
//Throw NoSuchElementException exception
throw new NoSuchElementException();
//Reference method unlinkfirst (node < E > F)
return unlinkFirst(f);
//In the unlikfirst (f) method, after the deletion operation occurs
//The relationship between the remaining nodes (first will be reinitialized)
//So f is always the new first node
}
removeLast()
//Delete a node from the end of the linked list
public E removeLast() {
//Get tail node
final Node<E> l = last;
//If the tail node is null
if (l == null)
//Throw NoSuchElementException exception
throw new NoSuchElementException();
//Reference method unliklast (node < E > F)
return unlinkLast(l);
//In the method unliklast (L), after the delete operation occurs
//The relationship between the remaining nodes (last will be reinitialized)
//So l is always the new tail node
}
addFirst(E e)
//Add a node at the head of the linked list
public void addFirst(E e) {
//Reference method linkfirst (E)
linkFirst(e);
//In the method linkFirst(e), after the addition operation occurs
//The relationship between the added node and the original node
//In fact, the added node is the new first node
//(first will be reinitialized)
}
addLast(E e)
//Add nodes at the end of the linked list
public void addLast(E e) {
//Reference method linklast (E)
linkLast(e);
//In the method linkLast(e), after the addition operation occurs
//The relationship between the added node and the original node
//In fact, the added node is the new tail node
//(last will be reinitialized)
}
contains(Object o)
//Judge whether there is a node containing the specified element o in the linked list
public boolean contains(Object o) {
//If the return value of the method indexOf(o) is - 1, it returns true; otherwise, it returns false
return indexOf(o) != -1;
}
Method of interface Queue
The characteristic of Queue is that it can only add elements at the tail and delete elements at the head. To sum up, it is "first in, first out"
add(E e)
//Reference method addlast (E)
//Add elements at the end of the linked list
public boolean add(E e) {
//Reference method linkLast()
linkLast(e);
return true;
}
remove(Object o)
//Traverse the linked list from left to right and delete elements and
//Specifies the first node where the elements o are equal
public boolean remove(Object o) {
//If o is null
if (o == null) {
//Traverse the linked list from left to right through the for loop, and x is the loop factor
//The initialization value of x is the first node, as long as x is not null
//Continue to assign the next node to X (step)
//After the first cycle, x changes from the first node to the second node
//And so on until you loop to the tail node
for (Node<E> x = first; x != null; x = x.next) {
//If the node element x.item is null
if (x.item == null) {
//Delete node
unlink(x);
return true;
}
}
//If o is not null
} else {
//ditto
for (Node<E> x = first; x != null; x = x.next) {
//If the node element x.item is equal to the specified element o
if (o.equals(x.item)) {
//Delete node
unlink(x);
return true;
}
}
}
//If the linked list is empty or does not contain
//Specify the element o, and directly terminate the program and return false
return false;
}
List interface method
get(int index)
//Returns the element of the node whose specified index is index
public E get(int index) {
//Check whether the index value index is valid
//If it is invalid, throw an exception directly
checkElementIndex(index);
//Reference method node(int index)
//Returns the element of the node
return node(index).item;
}
set(int index, E element)
//Replace the element of the node whose index value is index with the specified element element
public E set(int index, E element) {
//Check whether the index value index is valid
//If it is invalid, throw an exception directly
checkElementIndex(index);
//Reference method node(int index)
//Gets the node whose index value is index
Node<E> x = node(index);
//Gets the element oldVal of the node
E oldVal = x.item;
//Re assign element to the element of the node
x.item = element;
//Returns the element oldVal
return oldVal;
}
add(int index, E element)
//The node that will contain the specified element element
//Add index at the specified index position in the linked list
public void add(int index, E element) {
//Check whether the index value index is valid
//If it is invalid, throw an exception directly
checkPositionIndex(index);
//Determine the location of the added node according to the index value index
//Add at the end of the linked list
if (index == size)
//Reference method linkLast(int index)
linkLast(element);
//Add in the middle of the linked list
else
//Reference method node(int index)
//Reference method linkbefore (E, node < E > succ)
//Get the node whose index value is index first
//Then pass it into the method as an actual parameter
//Linkbefore (E, node < E > succ)
linkBefore(element, node(index));
}
remove(int index)
//Delete the node whose specified index value is index
public E remove(int index) {
//Check whether the index value index is valid
//If it is invalid, throw an exception directly
checkElementIndex(index);
//Reference method node(int index)
//Reference method unlink (node < E > x)
//Get the node whose index value is index first
//Then pass it into the method as an actual parameter
//Unlink (node < E > x)
return unlink(node(index));
}
node(int index)
//Returns a non empty node with the specified index value of index.
Node<E> node(int index) {
//This involves an operation to improve efficiency
//Because LinkedList is bidirectional, it can
//Start with the head or the tail
//So take half the length of the linked list as the standard, if index
//If it is greater than it, start from the tail. If index is less than it
//Start with the first part
//Consider the case where the index is less than half of the linked list
//Size > > 1 is equivalent to size/2
if (index < (size >> 1)) {
//Get the first node and start with it
//The direction is from left to right
Node<E> x = first;
//for loop
for (int i = 0; i < index; i++)
//Step expression
x = x.next;
//From the above loop, we can see the linked list
//Sequential access is characteristic of loops without any
//The judgment or conditional statement is just a simple loop
//Start from the first node and go through index-2
//Node before reaching the target node
//Return to target node x
return x;
//Consider the case where the index is greater than half of the linked list
} else {
//Get the tail node and start with it
//The direction is from right to left
Node<E> x = last;
for (int i = size - 1; i > index; i--)
//Step expression
x = x.prev;
//Return to target node x
return x;
}
}
indexOf(Object o)
//Returns an element that is o equal to the specified element
//Index value of the first node
//Traverse the linked list from the first node in the direction from left to right
public int indexOf(Object o) {
//Linked lists are accessed sequentially
//The index value of the first node is 0
int index = 0;
//Consider the case where the specified element o is null
if (o == null) {
//for loop traversal linked list
//The traversal direction is from left to right
for (Node<E> x = first; x != null; x = x.next) {
//If the element is null
if (x.item == null)
//Return index value
return index;
//If the element is not null
//Auto increment index value
index++;
}
//Consider the case where the specified element o is not null
} else {
//for loop traversal linked list
//The traversal direction is from left to right
for (Node<E> x = first; x != null; x = x.next) {
//If the element is equal to the specified element o
if (o.equals(x.item))
//Return index value
return index;
//If the element is not equal to the specified element o
//Auto increment index value
index++;
}
}
//If the linked list does not contain the specified element o, return - 1
return -1;
}
lastIndexOf(Object o)
//Returns an element that is o equal to the specified element
//Index value of the first node
//Traverse the linked list from the tail node in the direction from right to left
public int lastIndexOf(Object o) {
//Linked lists are accessed sequentially
//The index value of the first node is size
int index = size;
//Consider the case where the specified element o is null
if (o == null) {
//for loop traversal linked list
//The traversal direction is from right to left
for (Node<E> x = last; x != null; x = x.prev) {
//Note the difference from the method indexOf(Object o)
//lastIndexOf(Object o) decrements the index value first
//Then judge
index--;
//If the element is null
if (x.item == null)
//Return the index value index
return index;
}
//Consider the case where the specified element o is not null
} else {
//for loop traversal linked list
//The traversal direction is from right to left
for (Node<E> x = last; x != null; x = x.prev) {
//Decrement index value first
index--;
//If the element is equal to the specified element o
if (o.equals(x.item))
//Return the index value index
return index;
}
}
//If the linked list does not contain the specified element o, return - 1
return -1;
}
Method of class Stack
The characteristic of Queue is that it can only add elements at the tail and delete elements at the head. In summary, it is "last in, first out"
peek()
//Returns the element of the first node of the linked list
//If the first node is null, return null directly
public E peek() {
final Node<E> f = first;
//If f is null, null is returned; otherwise, element is returned
return (f == null) ? null : f.item;
}
element()
//Returns the element of the first node of the linked list
//If the first node is null, directly
//Throw NoSuchElementException exception
public E element() {
//Reference method getFirst()
return getFirst();
}
poll()
//Delete the first node after returning the element of the first node of the linked list
//If the first node is null, return null directly
public E poll() {
final Node<E> f = first;
//If f is null, null is returned
//Otherwise, the result of the method unlinkFirst(f) is returned
//Reference method unlinkfirst (node < E > F)
return (f == null) ? null : unlinkFirst(f);
}
remove()
//Delete elements at the head of the linked list
//If the first node is null, directly
//Throw NoSuchElementException exception
public E remove() {
//Reference method removeFirst()
return removeFirst();
}
offer(E e)
//Add nodes at the end of the linked list
public boolean offer(E e) {
//Reference method add (E)
return add(e);
}
offerFirst(E e)
//Add a node at the head of the linked list
public boolean offerFirst(E e) {
//Reference method addfirst (E)
addFirst(e);
return true;
}
offerLast(E e)
//Add nodes at the end of the linked list
public boolean offerLast(E e) {
//Reference method addfirst (E)
addLast(e);
return true;
}
peekFirst()
//Returns the element of the first node of the linked list
//If the first node is null, return null directly
public E peekFirst() {
final Node<E> f = first;
//If f is null, null is returned; otherwise, element is returned
return (f == null) ? null : f.item;
}
peekLast()
//Returns the element of the end node of the linked list
//If the first node is null, return null directly
public E peekLast() {
final Node<E> l = last;
//If f is null, null is returned; otherwise, element is returned
return (l == null) ? null : l.item;
}
pollFirst()
//Delete the first node after returning the element of the first node of the linked list
//If the first node is null, return null directly
public E pollFirst() {
final Node<E> f = first;
//If f is null, null is returned
//Otherwise, the result of the method unlinkFirst(f) is returned
//Reference method unlinkfirst (node < E > F)
return (f == null) ? null : unlinkFirst(f);
}
pollLast()
//Delete the tail node after returning the elements of the tail node of the linked list
//If the first node is null, return null directly
public E pollLast() {
final Node<E> l = last;
//If f is null, null is returned
//Otherwise, the result of the method unliklast (f) is returned
//Reference method unliklast (node < E > F)
return (l == null) ? null : unlinkLast(l);
}
push(E e)
//Add a node at the head of the linked list
public void push(E e) {
//Reference method addfirst (E)
addFirst(e);
}
pop()
//Delete elements at the head of the linked list
//If the first node is null, directly
//Throw NoSuchElementException exception
public E pop() {
//Reference method removeFirst()
return removeFirst();
}
listIterator(int index)
//Returns the list iterator starting at the specified index position index
public ListIterator<E> listIterator(int index) {
//Check whether the index value index is valid
//If it is invalid, throw an exception directly
checkPositionIndex(index);
//Returns an internal class ListItr object
return new ListItr(index);
}