Linked List

From Progteam

Revision as of 21:53, 27 March 2007 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A Linked List is an Abstract Data Structure.


Code Packet

This implementation of List has a very large number of optional features. Which ones are core and which are unnecessary are labeled. This should be loaded with a ton of optional functionality. Make sure the functions you add document their purpose.

This code is used by:

class List<T extends Comparable> implements Iterable<T>{

    /** Core stuff **/

    class Node{
        T el;
        Node next;
    }
    
    class Iter implements Iterator<T>{
        Node ptr;

        public boolean hasNext(){
            return ptr.next!=null;
        }
        public T next(){
            ptr=ptr.next;return ptr.el;
        }
        public void remove(){}

        /** Optional Methods **/

        /** A list containing all the unvisited elements including this one **/
        /** Note! The list returned by this cannot be modified! **/
        public List<T> getTail(){
            List<T> res=new List<T>();

            res.head=ptr;

            return res;
        }
    }

    Node head,tail;
    int size;

    public List(){
        head=new Node();
        tail=head;
        
        head.next=null;
        size=0;
    }

    public boolean add(T v){
     
        Node n=new Node();
        n.el=v;
        n.next=null;

        tail.next=n;
        tail=n;
        ++size;
        return true;
    }

    public Iter iterator(){
        Iter i=new Iter();
        i.ptr=head;
        return i;
    }

    /** Optional **/

    public boolean remove(T v){
        for(Node n=head;n.next!=null;n=n.next)
            if(n.next.el.equals(v)){
                n.next=n.next.next;
                --size;
                return true;
            }
        return false;
    }


    
    /** Stack Operations 
     *
     * Front of the list is the top
     */
   
    /** Adds to the front of the list.  Doesn't check for duplicates **/
    public void push(T x){
        Node n=new Node();

        n.el=x;
        n.next=head.next;
        head.next=n;

        ++size;
    }

    /** Removes and returns the first **/
    public T pop(){
        if(0==size)
            return null;
        T x=head.next.el;
        head.next=head.next.next;

        --size;

        return x;
    }

    /** Returns the top (the first) **/
    public T top(){
        if(0!=size)
            return head.next.el;
        return null;
    }

    /** Queue Operations 
     *
     * For peek and poll, use top() and pop()
     */

    /** Adds an element to the end **/
    public void enqueue(T x){
        Node n=new Node();

        n.el=x;
        n.next=null;

        tail.next=n;
        tail=n;

        ++size;
    }

    /** Sorting Related Options **/

    /** Assuming the list is sorted, insert the item into sorted order **/
    public void insertSorted(T x){
        Node tmp=head;

        while(true){
            if(null==tmp.next){
                Node n=new Node();

                n.el=x;
                n.next=null;
                tmp.next=n;
                return;
            }

            if((tmp.next.el).compareTo(x)>=0){
                Node n=new Node();

                n.el=x;
                n.next=tmp.next;
                tmp.next=n;

                return;
            }

            tmp=tmp.next;
        }
    }
}

Personal tools