Linked List

View Code

With a chain of Nodes a Linked List can be created. It is a basic container class and works like an array. However there are a few differences. First changing size is not a probelm. Second getting items may take longers than a normal array.

The Linked List can implement all the basic container functions, and becuause of its general form a find() and append() are included. Since the list consists of Nodes, pointers to Nodes are returned for functions that would return indexes if the List were an array. To help things a bit the Node class will have some helper member functions insertAfter(), and removeAfter().

Since the List will be created from Nodes head and tail are needed. Since it is dynamic an int for size would simplify things.


struct Node
{
   Node(int i=0, Node* n=NULL) : Data(i), Link(n) {}
   void insertAfter(int i) {link = new Node(i, NULL);)
   void removeAfter() {Node *temp; temp = link; link = link.link; delete temp;}
	 static Node* listCopy(Node* h);  //creates a deep copy of the list starting at h
	                                  //and returns a pointer to it

   int Data;
   Node* Link;
};

class LinkList
{
   public:
      LinkList() : head(NULL), tail(NULL), size(0) {}  
      LinkList(const LinkList& ll);                //copy constructor
      ~LinkList()                                      //destructor
			
      void add(int num);               //adds element to the end of the list
      Node* get(int index);            //gets the index-th element with zero offset
      void remove(int index);          //remove the index-th with zero offset
      void clear();                    //removes everything
      void append(const LinkList& ll);  //adds ll to end of list, shallow copy
			
      bool empty();          //true if empty
      int size();            //gets size
      Node* find(int num);   //returns pointer to Node with value of num
			
      LinkList& operator=(const LinkList& rhs);  //assignment

   private:
      Node* head;
      Node* tail;
      int size;
};

The implementation shouldn't be too hard. Only those with delete and copying could be tricky. It's best to do the function as if it were a general case, then if it was the first case. Finally put the two together with appropriate logic.

Function	Evaluation	Order
listCopy	Basic tranversal for linear order.	O(n)
LinkList()	Declare to pointer and an integer.	O(1)
LinkList(LinkList)	Same order as the assignment operator.	O(n)
~LinkLIst	Simple linerar deletion.	O(n)
add()	Simple Node declaration and variable manipulation at the tail. If there wasn't a tail this could have had linear traversals.	O(1)
remove()	Call to get for O(n) and simple opearations for O(n+1).	O(n)
clear()	Linear deletetion.	O(n)
append()	Just edit some pointers for constant order.	O(1)
empty()	Simple return.	O(1)
size()	Simple return.	O(1)
clear()	Simple assignments and deletion for O(1).	O(n)
find()	Traverse through the list for a linear order.	O(n)
=	Call listCopy, O(n). Then a simple traversal for tail, O(2n).	O(n)

From the function evalution the strengths and weakness of a Linked List are shown. It can change dynamicaly which a simple array cannot, but is slow in getting its values.

Another form of a linked list is the doubley linked list. It is the same except the Nodes have a pointer to the next and previous link. They make things easier for modifing, but can easily change to trees or graphs. (More one those latter).

Prev -- Back to Portal -- Next