线性链表

数组线性表的add（int index，Object o）和remove（int index）方法的效率很低，因为这两个方法需要移动潜在的大量元素。为提高在表中特意位置添加和删除元素的效率，可以采用链式结构来实现线性表。

MyLinkedList是使用链式结构实现的动态线性表，它扩展了MyAbstractList类。此外，它还提供addFirst、addLast、removeFirst、removeLast、getFirst和getLast方法，如下图

实现MyLinkedList

实现addFirst（e）方法

addFirst（e）方法创建一个包含元素e的新结点。该新结点就成为链表的第一个结点。该方法可以如下实现：

public void addFirst(E e) {
    Node<E> newNode = new Node<E>(e);
    newNode.next = head;
    head = newNode;
    size++;
    if(tail == null) rail = head;
}

 

 实现addLast（e）方法

 

addLast（e）方法创建一个包含元素的新结点，并将它插到链表的末尾。该方法可以如下实现：

public void addLast(E e) {
    Node<E> newNode = new Node<E>(e);
    if(tail == null) { 
        head = tail = newNode;
    } 
    else {
        tail.next = newNode;
        tail = tail.next; 
    }
    size++;
}

 

实现add（index,e)方法

 

add(index,e)方法将一个元素插入到链表的指定下标处。该方法可以如下实现：

public void add(int index, E e) {
    if(index == 0) addFirst(e);
    else if (index >= size) addLast(e);
    else {
        Node<E> Current = head;
        for(int i =1; i< index; i++) current = current.next;
        Node<E> temp = current.next;
        currrent.next = new Node<E>(e);
        size++;
    } 
}
 

 实现removeFirst（）方法

 

removeFirst（）方法从链表中删除第一个元素。该方法可以如下实现：

public E removeFirst () {
     if (size == 0) retrun null;
     else if (size == 1){
         Node<E> temp = head;
         head = tail = null;
         size = 0;
         return temp.element;
     } 
    else{
        Node<E> current = head; 
        head = (head.next).next;
        size--;
        return current.element；
    } 
}

 

实现removeLast（）方法

 

removeLast（）方法从链表中移走最后一个元素。该方法可以如下实现：

public E removeLast() {
    if (size == 0) return null;
    else if (size == 1) {
        Node<E> temp = head;
        head = tail = null;
        size = 0;
        rerurn temp.element;
    }
    else{
        Node<E> current = head;
        for(int i= 0; i < size -2; i++) current = current.next;
        Node<E> temp = tail;
        tail = current;
        tail.next = null;
        size --;
        rerurn temp.elelment;
    }
}

 

实现removo（index）方法

remove(index)方法找到指定下标处的结点，然后将它删除。该方法可以如下实现：

public E remove(int index) {
    if(index < 0 || index >= size) return null;
    else if (index == 0) return removeFirst();
    else if (index == size -1) return removeLast();
    else {
        Node<E> previous = head;
        for(int i = 1; i < index; i++) {
            previous = previous.next;
        }
        Node<E> current = previous.next;
        previous.next = current.next;
        size--;
        return current.element;
    }
}