Linked List Recall the properties of a list which were covered earlier.  There are a few drawbacks. insertion into a list required moving items to accommodate the insert items. in doing this it is possible to exceed the array size. This leads to a new version of the list using DMA called a linked list. The idea: Node: a node consists of data and structuring information( head, next, tail)   Things to do with nodes: - find - create - remove - cleanup Let's create a node in C++ form: class Node { public:      int data;      Node *next;      Node(int d=0, Node *p = 0);  // constructor with default args. }; Note that one of your data members is Node which is the type that you are currently creating.  This is a special case where this is permitted. Node::Node (int d, Node *p) {      data = d;          // this creates a completely      next = p;          // initialized Node } The idea of Linked lists is that you can allocate memory as you need them "on the fly". Nodes are pointers.  To implement you would use the following as an example: . . Node *head = new Node; head->next = 0;     // same as (*head).next Node *n = new Node; n->next = 0; Node *t = head;     // declares and sets to Node head while(t->next != 0)      t = t->next; t->next = n;  There is one major difference between a class and a struct in C++ : class -     by default, all members are private struct -    by default, all members are public knowing this information and wanting to be able to access the nodes within a list, lets write a struct called LNode: struct LNode {      int data;      LNode *next;      LNode(int d=0, LNode *n)  // uses default arguments }; LNode::LNode(int d, LNode *n) {      data = d;      next = n; } Now let's write the List Class: class List {      LNode *head; publilc:      List();      ~List();      int insert(int record);          // return is error code      int retrieve(int record);     // return is error code      int remove(int record);      void clear();      bool empty(); }; we won't write out the constructor or the empty functions again.  Just need to know that: constructor - sets head to zero empty - checks if *head is NULL.  If so, it's empty and returns true clear( ) Let's first concentrate on the clear( ).  It will be responsible to get rid of all the elements in the List.  It will go down the list one by one and free up.  *** keep track of the pointers!! *** set the additional pointer and point at each node. use that pointer to get at the next thing in the list and mark head. then delete the node void List::clear( ) {      LNode *rest;     // meaning rest of the list      // check for empty list already if (head==0)                     return;      // loop and delete      while (head)     // NULL would return false and indicate empty      rest = head->next;      delete head;      head = rest; } Note:  Once you delete memory it's free game for use by other persons or program executions on the computer.  Watch where you place your delete in this case.  It may not be a problem but if something else takes that memory space before you retrieve the information, you're toast.  It's good practice to get the pointers straightened out first and then to delete memory. You also need a destructor that does the same thing. List::~List() {      clear(); } You can often code like this when you are using DMA There is a positive side effect of using the head pointer in the function above.  By using it and "stepping back" as we delete, when we kick out of the loop head = NULL so it has re-initialized back to zero. There is another way to implement the destructor using recursion. Recursion:   recursion is an analytical tool of problem approach.  It is a function that calls itself. an example of a recursive function is as follows: void demo(int a) {      int b;      demo (a+1); } Look closely.  This function will cause BIG problems if you were to run it.  What really happens is that when the function is called it will allocate memory.  The recursive nature will continue to call the function on itself and continue to allocate memory for each additional instance.  The last call will be executed first so the memory keeps being chunked away until all system resources are annihilated  So how can we make recursion useful for our purposes?? A)    It allows you to break up problems into smaller problems of the same type. Example:  n! n! = n * (n-1) * (n-2) * (n-3) * ….* 3 * 2 * 1  so we could then say… n! = n * (n-1)! when coding this you must think about where you are going to stop and how to do it.  You will stop when you reach 1! which is equal to 1.  That is the smallest you can encounter. implementation: int factorial(int n) {      if(n==0)           return 1;      return n * factorial(n-1); } Why are we bringing up recursion now?  Because deleting a list can be turned into a recursion. Recursive version of deleting list: (recursive clear) List::r_clear(LNode *n) {      if(n==0)           return;      r_clear(n->next);      delete n; } BUT.. to use this we must first re-write the clear ( ) too. List::clear() {      r_clear(head);     // this jump starts the private method r_clear      head = 0 } Creating a List (inserting nodes) When you want to insert a node into a list, you need to know these things: is the list sorted or unsorted? should you control the location of the insert? Let's implement a version tacking on a node to the beginning of a list.  Remember that this operation is all about changing pointer values. void List::insert(int record) {      LNode *p;      p = new LNode(record)     // using default arguments here p->next = head; head = p; } What's really going on here?* first you are creating a pointer and assigning it DMA for the size of the record next you're telling the pointer to point to what *head points to next you're telling head to point to the new pointer you created. Inserting at the end of a list: The only real difference for inserting at the end of the list is that you have to loop through the list and check to see when you are at the end.  You need to start at the beginning of the list and step down to the bottom.  This is done in the following steps: You should create two pointers.  One as a search pointer and one for your previous location. start off with search = head and pred = 0. use the slinky effect to safeguard against Buss errors which are caused by "stepping off the end" of your list. Once you get to the end of the list (where search ==0) then you know you are at the end of the list and can insert the node in the position  of the pred->next.  Always be careful of the order of switching the pointers so you don't lose your nodes. Example: Node *search = head; Node *pred = 0; Node n; n = new Node(pass arguments here); // check to see if DMA created if (n==0)      return ERROR_CODE;     // return error code // search for end of list while (search !=0) {      pred = search;      search = search->next; } //check if head of list if(pred==0)      { n->next = search; head = n; return OK;     // return error code } // tack onto end of list n->next = search; pred->n = n; This code will take care of inserting a node at the end of a list.  It can be easily modified to insert at any given place in the list by changing the search condition and adding additional checks.  Always remember to check for errors and all possible conditions.  It's really easy to lose information when changing the pointers so be sure where you are before you change them. Deleting a node from a list: A deletion from a list is accomplished in much the same way as the insert.  The only difference is in your pointer manipulation once you find the node to remove.  Step through as follows: create two pointers (search and pred) and step through list same as in the insert. once you find the node to delete you set the pred->next to the search->next delete the search make sure you do it in this order otherwise you will lose all nodes after the one you are deleting.  The following is an example of deleting from the end of a list. Example: { Node *search,  *pred; search = head; pred = 0; //search for end of list while(search!=0) {      pred = search;      search = search->next; } // check for at head of list if(pred == head)      {      head = search->next;      delete search;      return OK;     // Error code } pred->next = search->next; delete search; } Doubly Linked Lists: If you create a doubly linked list it is much the same as previously mentioned except for the fact that each node has a previous and well as a next pointer.  It looks like this: Example: struct Node {      T data;      Node *next;      Node *perv; }; deleting an entire list is done recursively the same as with a singly linked list. Inserting into Doubly Linked List: Search through your list same as before until you establish the position you wish to insert. establish links from the new node first then and only then sever the original links. Don't let it confuse you.  Just remember that each node now has a previous and a next pointer. Inserting into the middle of a list takes making the  pointer switch like this: // connect new node n->next = search; n->prev = search->prev; //now sever ties search->prev->next = n; search->prev = n; Inserting at the head of a list takes making the pointer switch like this: n->next = head; n->prev = 0; head->prev = n; head = n; Inserting at the end of a list takes making pointer switch like this: // search to find end while(search!=0) {      pred = search;      search = search->next; } n = new Node(); n->prev = search; n->next = 0; search->next = n; Removing Node from Doubly Linked List: When you are deleting a node from a doubly linked list you only have two pointers to take care of. If you have three nodes named 1, 2, and 3 respectively and you want to remove node 2 from the list, you need to take the next pointer from node one to point to node 3 and the previous pointer from node three to point to node 1.  This is accomplished in the following manner using only one search pointer: search->next->prev = search->prev; search->prev->next = search->next; delete search; This is diagramed below: