ArrayList using
a linked list, in order to find the size of an arrayList we had to
run a pointer down the linked list links and count them. This is an
O(N) operation. If we had an integer variable in the arrayList object
which told us the number of items in the arrayList, we could give the
size just from this variable, which would be an O(1) operation. We would
have to ensure this variable is reduced by one every time an item is removed
from the arrayList, and increased by one every time an item is added.
We would also use it to tell in advance whether the operations to add
or remove an item from a particular position should throw an exception
because the position is beyond the size of the arrayList. Previously
we could only tell if we ran the pointer through the linked list and
it reached the end before the count of links traversed reached the desired
position.
So adding a variable in an object which implements ArrayList
using a linked list to store its size directly is not strictly necessary,
because that information can be worked out from the linked list.
However, it adds to the efficiency of the object, particularly if we
will be calling the method size on it frequently.
Here is the code for this modified implementation of ArrayList,
which can be found in the directory ~mmh/DCS128/code/linkedlists
in the file MyArrayList6.java.
class MyArrayList6 <E>
{
// Linked list implementation of ArrayList with size variable
private Cell<E> myList;
private int mySize;
public MyArrayList6()
{
myList=null;
mySize=0;
}
public E get(int pos)
{
Cell<E> ptr=myList;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
for(int count=0; count<pos; ptr=ptr.next, count++) {}
return ptr.first;
}
public void set(int pos,E item)
{
Cell<E> ptr=myList;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
for(int count=0; count<pos; ptr=ptr.next, count++) {}
ptr.first=item;
}
public void add(E item)
{
if(myList==null)
myList = new Cell<E>(item,null);
else
{
Cell ptr=myList;
for(; ptr.next!=null; ptr=ptr.next) {}
ptr.next = new Cell<E>(item,null);
}
mySize=mySize+1;
}
public void add(int pos,E item)
{
if(pos>mySize)
throw new IndexOutOfBoundsException();
if(pos==0)
myList = new Cell<E>(item,myList);
else
{
Cell<E> ptr=myList;
for(int count=1; count<pos; ptr=ptr.next,count++) {}
ptr.next = new Cell<E>(item,ptr.next);
}
mySize=mySize+1;
}
public E remove(int pos)
{
E item;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
else if(pos==0)
{
mySize=mySize-1;
item=myList.first;
myList=myList.next;
return item;
}
else
{
Cell<E> ptr=myList;
for(int count=1; count<pos; ptr=ptr.next,count++) {}
mySize=mySize-1;
item=ptr.next.first;
ptr.next=ptr.next.next;
return item;
}
}
public boolean remove(E item)
{
if(myList==null)
return false;
else if(item.equals(myList.first))
{
mySize=mySize-1;
myList=myList.next;
return true;
}
else
{
Cell<E> ptr=myList;
for(; ptr.next!=null&&!item.equals(ptr.next.first); ptr=ptr.next) {}
if(ptr.next==null)
return false;
else
{
mySize=mySize-1;
ptr.next = ptr.next.next;
return true;
}
}
}
public int size()
{
return mySize;
}
public int indexOf(E item)
{
int count=0;
Cell<E> ptr=myList;
for(; ptr!=null&&!item.equals(ptr.first); ptr=ptr.next, count++) {}
if(ptr==null)
return -1;
else
return count;
}
public int lastIndexOf(E item)
{
int pos=-1;
Cell<E> ptr=myList;
for(int count=0; ptr!=null; ptr=ptr.next, count++)
if(item.equals(ptr.first))
pos=count;
return pos;
}
public String toString()
{
String str="[";
if(myList!=null)
{
str+=myList.first;
for(Cell<E> ptr=myList.next; ptr!=null; ptr=ptr.next)
str+=","+ptr.first;
}
return str+"]";
}
private static class Cell <T>
{
T first;
Cell<T> next;
Cell(T h,Cell<T> t)
{
first=h;
next=t;
}
}
}
You can see that the variable mySize is increased by one in the
add operations, and decreased by one in the remove
operations except when the item to be removed is given as the argument and
is not found in the arrayList. The add and remove
methods which take an integer giving a position in the arrayList as their
argument throw an IndexOutofBoundsException if this is
beyond the size of the arrayList as given by mySize.
The exception is thrown before the mySize variable
has its value changed, so its value does not get changed in these cases.
Note that with remove the index must be less than the
size of the arrayList, but with add it can be equal
to the size, indicating adding a new item at the end. The get
and set methods also throw an IndexOutofBoundsException
if their argument is beyond the size of the arrayList as given by the
mySize, whereas previously they had to go through the whole
linked list to discover that an index beyond the size of the arrayList had
been given as the argument.
add. This always adds the item given as its argument
to the end of the collection. With the linked list implementation, to find
the end we have to start with a pointer at the beginning of the linked list
and move it all the way down the list until it points to a cell whose
next variable is null. If we had a pointer
kept in the object to the last cell in the array, we could add an item
to the back in one step, rather than have to go right through the array -
again O(1) instead of O(N). This means the diagram used to represent the
arrayList written textually as [5,8,3,4] and referred
to by variable a would be:
We are keeping the variable with the size of the arrayList in our implementation, so it is shown as part of the object in our diagram.
This representation gives the following code which can be found in the file MyArrayList7.java:
class MyArrayList7 <E>
{
// Linked list implementation of ArrayList with size variable and pointer
// to back
private Cell<E> myList,back;
private int mySize;
public MyArrayList7()
{
myList=null;
back=null;
mySize=0;
}
public E get(int pos)
{
Cell<E> ptr=myList;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
for(int count=0; count<pos; ptr=ptr.next, count++) {}
return ptr.first;
}
public void set(int pos,E item)
{
Cell<E> ptr=myList;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
for(int count=0; count<pos; ptr=ptr.next, count++) {}
ptr.first=item;
}
public void add(E item)
{
if(myList==null)
{
myList = new Cell<E>(item,null);
back = myList;
}
else
{
back.next = new Cell<E>(item,null);
back = back.next;
}
mySize=mySize+1;
}
public void add(int pos,E item)
{
if(pos>mySize)
throw new IndexOutOfBoundsException();
if(pos==0)
{
myList = new Cell<E>(item,myList);
if(mySize==0)
back=myList;
}
else
{
Cell<E> ptr=myList;
for(int count=1; count<pos; ptr=ptr.next,count++) {}
ptr.next = new Cell<E>(item,ptr.next);
if(ptr==back)
back=ptr.next;
}
mySize=mySize+1;
}
public E remove(int pos)
{
E item;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
else if(pos==0)
{
if(mySize==1)
back=null;
item=myList.first;
myList=myList.next;
}
else
{
Cell<E> ptr=myList;
for(int count=1; count<pos; ptr=ptr.next,count++) {}
item=ptr.next.first;
if(ptr.next==back)
back=ptr;
ptr.next=ptr.next.next;
}
mySize=mySize-1;
return item;
}
public boolean remove(E item)
{
if(myList==null)
return false;
else if(item.equals(myList.first))
{
mySize=mySize-1;
myList=myList.next;
return true;
}
else
{
Cell<E> ptr=myList;
for(; ptr.next!=null&&!item.equals(ptr.next.first); ptr=ptr.next) {}
if(ptr.next==null)
return false;
else
{
mySize=mySize-1;
if(ptr.next==back)
back=ptr;
ptr.next = ptr.next.next;
return true;
}
}
}
public int size()
{
return mySize;
}
public int indexOf(E item)
{
int count=0;
Cell<E> ptr=myList;
for(; ptr!=null&&!item.equals(ptr.first); ptr=ptr.next, count++) {}
if(ptr==null)
return -1;
else
return count;
}
public int lastIndexOf(E item)
{
int pos=-1;
Cell<E> ptr=myList;
for(int count=0; ptr!=null; ptr=ptr.next, count++)
if(item.equals(ptr.first))
pos=count;
return pos;
}
public String toString()
{
String str="[";
if(myList!=null)
{
str+=myList.first;
for(Cell<E> ptr=myList.next; ptr!=null; ptr=ptr.next)
str+=","+ptr.first;
}
return str+"]";
}
private static class Cell <T>
{
T first;
Cell next;
Cell(T h,Cell<T> t)
{
first=h;
next=t;
}
}
}
The pointer to the back cell, called back, is used directly
in the single-argument add method which adds a new item
to the back of an arrayList: back.next is set to refer
to the new cell and back is then set to refer to this new
cell. However, back also needs to be reset in other cases
where the last item of the arrayList is changed. This happens when
add with two arguments is called, and the first argument
giving the position the new item is added happens to be the same as the
size of the arrayList. It also happens when one of the remove
methods is called and it happens to be the case that the item removed is
the last one in the arrayList. In this case, the back pointer
has to be reset to point to the cell before the old last cell in the
list. There is no statement that can do this directly, since the
next variable of linked list cells points only forward.
In both these cases a pointer is run down the list to point
to the cell before the one to be removed, and the back
pointer is reset to the final value of this pointer.
next and
prev. If you start from the front of the list and follow
the next pointers until you come to a cell whose
next pointer is null, you will have gone right
through the list in the normal direction. However, if you start from the
back of the list and follow the prev pointers until you come
to a cell whose prev pointer is null, you
will have gone through the list in reverse.
Here is how the arrayList
[5,8,4,3] is represented
diagrammatically when this implementation technique is used:
Cell has to be
declared such that Cell objects have three variables
in them, the forward and backward pointers called next and
prev and the data of the cell in the variable
called data. The code is similar to before, but when an
item is added to or deleted from the arrayList, the links need to be
carefully set to maintain the doubly-linked property.
Here is complete code for an arrayList implemented as a doubly-linked list:
class MyArrayList8 <E>
{
// Doubly linked list implementation of ArrayList
private Cell<E> front,back;
private int mySize;
public MyArrayList8()
{
front=null;
back=null;
mySize=0;
}
public E get(int pos)
{
Cell<E> ptr=front;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
for(int count=0; count<pos; ptr=ptr.next, count++) {}
return ptr.data;
}
public void set(int pos,E item)
{
Cell<E> ptr=front;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
for(int count=0; count<pos; ptr=ptr.next, count++) {}
ptr.data=item;
}
public void add(E item)
{
if(front==null)
{
front = new Cell<E>(item,null,null);
back = front;
}
else
{
back.next = new Cell<E>(item,null,back);
back = back.next;
}
mySize=mySize+1;
}
public void add(int pos,E item)
{
if(pos>mySize)
throw new IndexOutOfBoundsException();
if(pos==0)
{
front = new Cell<E>(item,front,null);
if(mySize==0)
back=front;
else
front.next.prev=front;
}
else
{
Cell<E> ptr=front;
for(int count=1; count<pos; ptr=ptr.next,count++) {}
ptr.next = new Cell<E>(item,ptr.next,ptr);
if(ptr==back)
back=ptr.next;
else
ptr.next.next.prev=ptr.next;
}
mySize=mySize+1;
}
public E remove(int pos)
{
E item;
if(pos>=mySize)
throw new IndexOutOfBoundsException();
else if(pos==0)
{
mySize=mySize-1;
if(mySize==0)
back=null;
item=front.data;
if(front.next!=null)
front.next.prev=null;
front=front.next;
return item;
}
else
{
Cell<E> ptr=front;
for(int count=1; count<pos; ptr=ptr.next,count++) {}
mySize=mySize-1;
item=ptr.next.data;
if(ptr.next==back)
{
back=ptr;
ptr.next=null;
}
else
{
ptr.next.next.prev=ptr;
ptr.next = ptr.next.next;
}
return item;
}
}
public boolean remove(E item)
{
if(front==null)
return false;
else if(item.equals(front.data))
{
mySize=mySize-1;
if(front.next!=null)
front.next.prev=null;
front=front.next;
return true;
}
else
{
Cell<E> ptr=front;
for(; ptr.next!=null&&!item.equals(ptr.next.data); ptr=ptr.next) {}
if(ptr.next==null)
return false;
else
{
mySize=mySize-1;
if(ptr.next==back)
{
back=ptr;
ptr.next=null;
}
else
{
ptr.next.next.prev=ptr;
ptr.next = ptr.next.next;
}
return true;
}
}
}
public int size()
{
return mySize;
}
public int indexOf(E item)
{
int pos=0;
Cell<E> ptr=front;
for(; ptr!=null&&!item.equals(ptr.data); ptr=ptr.next, pos++) {}
if(ptr==null)
return -1;
else
return pos;
}
public int lastIndexOf(E item)
{
int pos=mySize-1;
Cell<E> ptr=back;
for(; ptr!=null&&!item.equals(ptr.data); ptr=ptr.prev, pos--) {}
return pos;
}
public String toString()
{
String str="[";
if(front!=null)
{
str+=front.data;
for(Cell<E> ptr=front.next; ptr!=null; ptr=ptr.next)
str+=","+ptr.data;
}
return str+"]";
}
private static class Cell <T>
{
T data;
Cell<T> next,prev;
Cell(T d,Cell<T> n,Cell<T> p)
{
data=d;
next=n;
prev=p;
}
}
}
As an example of linking together the cells to make a doubly linked list,
consider we have the case of the diagram
above
illustrating the variable a referring to an arrayList
object which implements the arrayList [5,8,4,3] using
a doubly linked list. Suppose we make the call a.add(2,9)
where this is the situation. This is adding 9 into the
position indexed by 2 in the arrayList, and pushing everything
in later positions up one place. The writer of the code which makes this
call thinks of it as just causing [5,8,4,3] to become
[5,8,9,4,3]. Within the code, this is implemented by
first running a pointer down the next links until it points
to the cell before the one where the new item is to be added in. The
following code fragment from the add method does this:
Cell ptr=front;
for(int count=1; count<pos; ptr=ptr.next,count++) {}
and in this example, it will lead to the situation illustrated
diagrammatically as:
The ptr.next variable is then set to refer to a new
cell, whose data is the item to be added (9 in this case),
whose next variable is the old value of ptr.next
and whose prev variable refers to the same cell as ptr.
This is done by the code fragment:
ptr.next = new Cell(item,ptr.next,ptr);
and results in the situation that can be shown diagrammatically as:
The new cell has not been added right at the end, so the back
variable does not have to be changed. But the prev
variable of the cell which is now two links down from ptr
needs to be changed so that instead of referring to the cell referred to
by ptr, it refers to the new cell which is next in the list
and so is given by ptr.next. This is done by the code:
ptr.next.next.prev=ptr.next
resulting in the situation represented diagrammatically by:
which you can see has 9 correctly linked into the
doubly linked list. Remember that the position of the cells in the
diagram has no meaning, the meaning is in the boxes from which the arrows come
and the cells to which they lead. The above diagram means the same as one
where the cells are laid out in a neat list. But this is not quite correct.
In order to get the complete final representation, the statement
mySize=mySize+1has to be executed to change the
mySize variable of the arrayList
object from 4 to 5.
You can see that it is important that the variables within the arrayList
object are declared as private. This means that no code
apart from the methods in the class of the object can change them.
For example, it is important that the variable mySize is
always left giving the correct number of cells in the linked list.
This ensures the methods always function properly when called.
LinkedList typeLinkedList
where the code underneath, provided by the suppliers of Java,
is very like the code described above using doubly-linked lists. It
differs in being slightly more efficient because the code always checks
which is the closest end of the list to start when accessing cells in it,
and then moves along either the next or prev
links. Our code given above always starts at the front and moves
down the next links except for the
method add with one argument which is known to add to the back.
The code underneath for Java's type ArrayList is
like that we described previously
using an "array and count" technique.
The reason is that one implementation may be more efficient for some
purposes, the other implementation may be more efficient for others.
The operation of getting or setting the value at a particular index
is more efficient using ArrayList because it is done
in one step when there is an array underneath, whereas it requires
moving down the links when there is a list underneath. But the operation
of adding an element at a particular position is
more efficient using LinkedList because, as we have
seen, linking a new cell into a linked list does not involve changing
the position of all other cells, whereas adding a new value into
an array involves "moving up" all elements after it. For similar
reasons, removing an element from a particular position is more
efficient using LinkedList than ArrayList.
So even though you can't change the code that Java provides for you,
it helps to know what's underneath in order to be able to choose
what is the more efficient form to use for your particular needs.
If you want a flexible indexed collection of elements, consider what
you want to do with it. If the main thing you will be doing is
looking up elements at particular indexes, but you won't be changing
the size much by inserting or removing elements at particular indexes,
use ArrayList. If you're going to do a lot of adding or
removing in the middle of the collection, but not much looking up
an index without changing the collection, it would be better
to use LinkedList.
Last modified: 17 March 2006