package com.learn.list;
import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
public class MyLinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size=0;
transient Node<E> first;
transient Node<E> last;
public MyLinkedList(){
}
public MyLinkedList(Collection<? extends E> c) {
this();
// addAll(c);
}
/**
* Link e as first element
* @param e
*/
private void linkFirst(E e){
final Node<E> f=first;
final Node<E> newNode=new Node<E>(null,e,f);
first=newNode;
if(f==null)
last=newNode;
else
f.prev=newNode;
size++;
modCount++;
}
/**
* Link e as last element
* @param e
*/
private void linkLast(E e){
final Node<E> l=last;
final Node<E> newNode=new Node<E>(l,e,null);
last=newNode;
if(l==null)
first=newNode;
else
l.next=newNode;
size++;
modCount++;
}
/**
* Insert element e before non-null Node succ
* @param e
* @param succ
*/
private void linkBefore(E e,Node<E> succ){
//assert succ!=null
final Node<E> pred=succ.prev;
final Node<E> newNode=new Node<E>(pred,e,succ);
succ.prev=newNode;
if(pred==null)
first=newNode;
else
pred.next=newNode;
size++;
modCount++;
}
/**
* Unlinks non-null first node f
* @param f
* @return
*/
private E unlinkFirst(Node<E> f){
//assert f==fisrt&& f!=null
final E element=f.item;
final Node<E> next=f.next;
f.item=null;
f.next=null;//help GC
first=next;
if(next==null)
last=null;
else
next.prev=null;
size--;
modCount++;
return element;
}
/**
* unlinks non-null last node l
*/
private E unlinkLast(Node<E> l){
//assert l==last&&l!=null
final E element =l.item;
final Node<E> prev=l.prev;
l.item=null;
l.prev=null;
last=prev;
if(prev==null)
first=null;
else
prev.next=null;
size--;
modCount++;
return element;
}
/**
* unlinks non-null node x
* @param x
* @return
*/
private E unlink(Node<E> x){
//assert x!=null
final E element =x.item;
final Node<E> next=x.next;
final 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;
}
/**
* return the first element in this list
*/
public E getFirst(){
final Node<E> f=first;
if(f==null)
throw new NoSuchElementException();
return f.item;
}
/**
* return the last element in this list
*/
public E getLast(){
final Node<E> l=last;
if(l==null)
throw new NoSuchElementException();
return l.item;
}
/**
* removes and returns the first element from this list
*/
@Override
public E removeFirst() {
final Node<E> f=first;
if(f==null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* removes and returns the first element from this list
*/
@Override
public E removeLast() {
final Node<E> l=last;
if(l==null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Insert the specified element at the beginning of this list;
*
*/
@Override
public void addFirst(E e) {
linkFirst(e);
}
/**
* appends the specfied element at end of this list
*/
@Override
public void addLast(E e) {
linkLast(e);
}
/**
* appends the specfied element at end of this list
*/
public boolean add(E e){
linkLast(e);
return true;
}
/**
* Inserts the specified element at the front of this list.
*/
@Override
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* Inserts the specified element at the end of this list.
*/
@Override
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* Retrieves and removes the first element of this list,
*/
@Override
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Retrieves and removes the last element of this list,
*/
@Override
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
@Override
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
@Override
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
/**
* Removes the first occurrence of the specified element in this list
*/
@Override
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/**
* removes the last occurrence of the specified element in this list
*/
@Override
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* Adds the specified element as the tail of this list
*/
@Override
public boolean offer(E e) {
return add(e);
}
@Override
public E remove() {
return removeFirst();
}
/**
* removes the first occurrence of the specified element from this list
* if it is present .if this list does not contain the element,it is
* unchanged
*/
public boolean remove(Object o){
if(o==null){
for(Node<E> x=first;x!=null;x=x.next){
if(x.item==null){
unlink(x);
return true;
}
}
}else{
for(Node<E> x=first;x!=null;x=x.next){
if(o.equals(x.item)){
unlink(x);
return true;
}
}
}
return false;
}
/**
* Appends all of the elements in the specified collection to the end of
* this list
*/
public boolean addAll(Collection<? extends E> c){
return addAll(size,c);
}
/**
* Inserts all of the elements in the specified collection into this list
* starting at the specified position
*/
public boolean addAll(int index,Collection<? extends E> c){
checkPositionIndex(index);
Object[] a=c.toArray();
int numNew=a.length;
if(numNew==0)
return false;
Node<E> pred,succ;
if(index==size){
succ=null;
pred=last;
}else{
succ=node(index);
pred=succ.prev;
}
for (Object object : a) {
@SuppressWarnings("unchecked")
E e=(E)object;
Node<E> newNode=new Node<>(pred,e,null);
if(pred==null)
first=newNode;
else
pred.next=newNode;
pred=newNode;
}
if(succ==null){
last=pred;
}else{
pred.next=succ;
succ.prev=pred;
}
size+=numNew;
modCount++;
return false;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
/**
* Tells if the argument is the index of an existing element.
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* Tells if the argument is the index of a valid position for an
* iterator or an add operation.
*/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* removes all of the elements from this list
*/
public void clear(){
for(Node<E> x=first;x!=null;){
Node<E> next=x.next;
x.item=null;
x.next=null;
x.prev=null;
x=next;
}
first=last=null;
size=0;
modCount++;
}
public E get(int index){
checkElementIndex(index);
return node(index).item;
}
/**
* replaces the element at the specified position in this list with the specified element
*/
public E set(int index,E element){
checkElementIndex(index);
Node<E> x=node(index);
E oldVal=x.item;
x.item=element;
return oldVal;
}
/**
* Inserts the specified element at the specified position in this list
*/
public void add(int index,E element){
checkPositionIndex(index);
if(index==size)
linkLast(element);
else
linkBefore(element,node(index));
}
/**
* removes the element at the specified position in this list
* @param index
* @return
*/
public E reomve(int index){
checkElementIndex(index);
return unlink(node(index));
}
public int indexOf(Object o){
int index=0;
if(o==null)
for(Node<E> x=first;x!=null;x=x.next){
if(x.item==null)
return index;
index++;
}
else
for(Node<E> x=first;x!=null;x=x.next){
if(o.equals(x.item))
return index;
index++;
}
return -1;
}
public int lastIndexOf(Object o){
int index=size;
if(o==null){
for(Node<E> x=last;x!=null;x=x.prev)
{
index--;
if(x.item==null)
return index;
}
}else{
for(Node<E> x=last;x!=null;x=x.prev)
{
index--;
if(o.equals(x.item))
return index;
}
}
return -1;
}
/**
* retrives and removes the head(first element) of this list
*/
@Override
public E poll() {
final Node<E> f=first;
return (f==null)?null:unlinkFirst(f);
}
@Override
public E element() {
return getFirst();
}
/**
* retrieves,but does not remove,the head(first element) of this list
*/
@Override
public E peek() {
final Node<E> f=first;
return (f==null)?null:f.item;
}
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*/
@Override
public void push(E e) {
addFirst(e);
}
/**
* Pops an element from the stack represented by this list.
* In other words,removes and returns the first element of this list
*/
@Override
public E pop() {
return removeFirst();
}
@Override
public int size() {
return size;
}
public static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
@Override
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
@Override
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E>{
private Node<E> lastReturned=null;
private Node<E> next;
private int nextIndex;
private int expectedModCount=modCount;
ListItr(int index){
next=(index==size)?null:node(index);
nextIndex=index;
}
@Override
public boolean hasNext() {
return nextIndex<size;
}
@Override
public E next() {
checkForComodification();
if(!hasNext())
throw new NoSuchElementException();
lastReturned=next;
next=next.next;
nextIndex++;
return lastReturned.item;
}
@Override
public boolean hasPrevious() {
return nextIndex>0;
}
@Override
public E previous() {
checkForComodification();
if(!hasPrevious())
throw new NoSuchElementException();
lastReturned=next=(next==null)?last:next.prev;
nextIndex--;
return lastReturned.item;
}
@Override
public int nextIndex() {
return nextIndex;
}
@Override
public int previousIndex() {
return nextIndex-1;
}
@Override
public void remove() {
checkForComodification();
if(lastReturned==null)
throw new IllegalStateException();
Node<E> lastNext=lastReturned.next;
unlink(lastReturned);
if(next==lastReturned)
next=lastNext;
else
nextIndex--;
lastReturned=null;
expectedModCount++;
}
@Override
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
@Override
public void add(E e) {
checkForComodification();
lastReturned=null;
if(next==null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/**
* Adapter to provide descending iterators via ListItr.previous
*/
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
@SuppressWarnings("unchecked")
private MyLinkedList<E> superClone() {
try {
return (MyLinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
/**
* Returns a shallow copy of this {@code LinkedList}. (The elements
* themselves are not cloned.)
*
* @return a shallow copy of this {@code LinkedList} instance
*/
public Object clone() {
MyLinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
public Object[] toArray(){
Object[] result=new Object[size];
int i=0;
for(Node<E> x=first;x!=null;x=x.next)
result[i++]=x.item;
return result;
}
public <T> T[] toArray(T[] a){
if(a.length<size)
a=(T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i=0;
Object[] result=a;
for(Node<E> x=first;x!=null;x=x.next)
result[i++]=x.item;
if(a.length>size)
a[size]=null;
return a;
}
}