Lists
—–
Store a list of integers as an array.
Disadvantages:
1. Suppose you want to insert an item at beginning or middle of the list. This takes time propotional to the length of the array.
2. Arrays have a fixed length.
public class List{
int[] a; // a reference
int lastItem; // index to the last item of the list
public List(){
a = new int[10];
lastItem = -1;
}
public void insertItem( int newItem, int location){ // inserts a new item at a location in the list
int i;
for(i = lastItem; i>= location; i--){ // this moves all the items in the list towards the right till the location is emptied
a[i+1] = a[i];
}
a[location] = newItem; // puts the newItem value into the empty location slot
lastItem++; // increment number of items
}
}
Linked Lists ; A recursive data type
—————————————
1. A list that is made up of data structures called nodes.
2. Each node stores two things:
– an item
– a reference to the next node in the list
public class ListNode{
int item;
ListNode next; // a reference called next pointing to next node in the list
}
// creating 3 different nodes
ListNode l1 = new ListNode();
ListNode l2 = new ListNode();
ListNode l3 = new ListNode();
// initialising values for items
l1.item = 10; // giving a value for item for l1
l2.item = 100;
l3.item = 1000;
//linking the nodes
l1.next = l2; // this links the lists
l2.next = l3;
l3.next = null; // l3 does not point to anything
Node operations
—————–
// the constructor for the ListNode
public ListNode(int item, ListNode next){
this.item = item;
this.next = next;
}
// for the last node
public ListNode(int item){
this(item, null);
}
ListNode node1 = ListNode(7, new ListNode(0, new ListNode(6)));
Advantages over arrays
————————-
1. Inserting an item in the middle of the linked list takes constant amount of time if you have a reference to previous node.
2. Moreover, the list can keep growing until the memory runs out.
Inserting a new item after “this”
public void insertAfter(int item){
next = new ListNode(item, next); // the later "next" is the older value on whatever object we can like l2
}
l2.insertAfter(2);
The last statement creates a new node with the item value 2 and the next parameter is the next value of l2( old ) which points to l3. Now the new “next” value is assigned to the newly created node.
Disadvantages
—————
1. Finding the nth item of the linked list takes time propotional to the length of the list n, number of items in the list. With arrays you can do this in constant time.
// to find the nth item in a list
public ListNode nth( int location){
if(position == 1){ // the current item
return this;
}else if ((position < 1) || ( next == null)){ // error checking
return null;
}else{
// we will use recursion
return next.nth(position -1); // -1 as we the list size keeps on decreasing
}
}
ListNode l2 = l.nth(4);
Lists of objects
—————–
1. Reference any object by declaring a reference of type Object.
public class SListNode{ // a singly linked list
public Object item;
public SLinkNode next;
}
A List Class
————-
There are 2 problems with SListNodes:
1. Insert new item at the begining of the list.
x = new SListNode("Soap", x); // problem when two references to same node
2. How do you represent an empty list?
x = null; // runtime error if you try to call any method on x
Solutions
———-
1. Seperate SList class that maintains the head of the list.
public class SList{
private SListNode head; // points to the beginning of the linked list
private int size; // keeps track of the number of SListNodes
public SList(){ // initialisation
head = null; // the idea of an empty list.
size = 0;
}
public void insertFront(Object item){ // we now insert it here and not in SListNode
head = new SListNode(item, head);
size++;
}
}
LinuxJunkies 