cpppro

Archive for December, 2006|Monthly archive page

Data structures lectures

In Data Structures in C/C++ on December 22, 2006 at 1:33 pm
       

Date

Title
View archived webcast
Wed, 01/18 Course Introduction
View archived webcast
Fri, 01/20 Developing a Simple Program
View archived webcast
Mon, 01/23 Containers
View archived webcast
Wed, 01/25 Pointer Manipulation
View archived webcast
Fri, 01/27 Arrays and Objects
View archived webcast
Mon, 01/30 Arrays and Objects (con’t)
View archived webcast
Wed, 02/01 Java Library List Classes
View archived webcast
Fri, 02/03 Object-Oriented Mechanisms
View archived webcast
Mon, 02/06 Abstract Methods and Classes
View archived webcast
Wed, 02/08 Abstract Methods and Classes con’t.
View archived webcast
Fri, 02/10 Examples of Interfaces
View archived webcast
Mon, 02/13 More on constructors, Exceptions
View archived webcast
Wed, 02/15 Loose ends: Packages, imports, access control, nested classes, super, instanceof
View archived webcast
Fri, 02/17 Loose ends: Packages, imports, access control, nested classes, super, instanceof (con’t)
Mon, 02/20 President’s Day
View archived webcast
Wed, 02/22 Delagation and Wrappers
View archived webcast
Fri, 02/24 Algorithmic Analysis I
View archived webcast
Mon, 02/27 Data Structures
View archived webcast
Wed, 03/01 Collections overview
View archived webcast
Fri, 03/03 Collections Overview (con’t)
View archived webcast
Mon, 03/06 Trees
View archived webcast
Wed, 03/08 Trees (con’t)
View archived webcast
Fri, 03/10 Tree representation, searching
View archived webcast
Mon, 03/13 Generic Programming
View archived webcast
Wed, 03/15 Priority queues, range queries
View archived webcast
Fri, 03/17 Hashing
View archived webcast
Mon, 03/20 Sorting I
View archived webcast
Wed, 03/22 Sorting II
View archived webcast
Fri, 03/24 Balanced Search Structures I
Mon, 03/27 Spring Break
Wed, 03/29 Spring Break
Fri, 03/31 Spring Break
View archived webcast
Mon, 04/03 Balanced Search Structures
View archived webcast
Wed, 04/05 Balanced Search Structures 2
View archived webcast
Fri, 04/07 Pseudo-Random Sequences
View archived webcast
Mon, 04/10 Threads, Concurrency
View archived webcast
Wed, 04/12 Balanced Search Structures
View archived webcast
Fri, 04/14 Backtracking search, game trees
View archived webcast
Mon, 04/17 Search and Game Trees (con’t), Enumeration Types
View archived webcast
Wed, 04/19 Graphs, Introduction
View archived webcast
Fri, 04/21 Graphs, more Algorithms
View archived webcast
Mon, 04/24 Algorithms (con’t)
View archived webcast
Wed, 04/26 Dynamic Programming
View archived webcast
Fri, 04/28 Storage Management
View archived webcast
Mon, 05/01 Garbage Collection
View archived webcast
Wed, 05/03 GUI Interfaces
Fri, 05/05 No Webcast
View archived webcast
Mon, 05/08 Course Summary

 

Audio, video lectures on data structres

 [tags]audio/video lectures on data structres, data structres lectures, data structures[/tags]

Double Linked List With Out Using Special Head or Tail Node

In C Tidbits, Data Structures in C/C++ on December 10, 2006 at 3:27 pm

Double linked list is a chain of nodes, each node’s next pointer point to next object and previous pointer points to previous node, here it is graphically…

 double linked list - 1

here is a c structure for double linked list’s node

struct Node
{
  void* info; //data
  Node* next; //used to point to next node
  Node* prev; //used to point to previous node
};

double linked list can be implemented using a special head node or without it. Special nodes act as header and tail, every time we perform an operation on list we give the special nodes. The disadvantage of using special nodes is extra space consumed by these nodes. Without special nodes, whenever we perform operations double linked list, we should be bit more careful.

This implementation deosn’t use special nodes.

Lets see how to insert a node in double linked list

double linked list - insertion

 here is the code for inserting a node before a known node

//insert before a known node and return the inserted node
Node *insertbefore(Node *before, void *data)
{
  Node* n;
  n = (Node *) malloc (sizeof(Node));
  n->info = data;

  //incase header node is not created
  if (!before)
  {
    n->prev = NULL;
    n->next = NULL;
    return n;
  }

  n->prev = before->prev;
  n->next = before;
  if (before->prev)
  {
    before->prev->next = n;
  }
  before->prev = n;

  return n;
}

the below code segment inserts after a known node in double linked list


//insert after a known node and return the inserted node
Node *insertafter(Node *after, void *data)
{
  Node* n;
  n = (Node *) malloc (sizeof(Node));
  n->info = data;

  //incase header node is not created
  if (!after)
  {
    n->prev = NULL;
    n->next = NULL;
    return n;
  }

  n->prev = after;
  n->next = after->next;

  if (after->next)
  {
    after->next->prev = n;
  }
  after->next = n;
  return n;
}

now lets see how to delete a node in double linked list

 

double linked list - deletion

 here is the code deleteting a node before and after a known node…

  //delete before a known node and return the node before deleted node
Node *deletebefore(Node *before)
{
  Node* tmp;

  tmp = before->prev;

  before->prev = tmp->prev;
  if (tmp->prev)
  {
    tmp->prev->next = before;
  }
  free(tmp);

  return before->prev;
}

//delete after a known node and return the node after deleted node
Node *deleteafter(Node *after)
{
  Node* tmp;

  tmp = after->next;

  after->next = tmp->next;
  if (tmp->next)
  {
    tmp->next->prev = after;
  }
  free(tmp);

  return after->next;

}

here is the routine for deleting entire double linked list, we can give any node in double linked list to delete entire list

//given any node in list, deletes entire double linked list
int deletelist(Node *n)
{
  Node *tmp;
  Node* after = n;
  Node* before = n->prev;

  //delete all nodes after n (if any)
  while(after)
  {
    tmp = after->next;
    free(after);
    after = tmp;
  }

  //delete all nodes before n (if any)
  while(before)
  {
    tmp = before->prev;
    free(before);
    before = tmp;
  }

  return 0;
}

the below routine searches entire double linked list given any node (not necessarily head node or tail node)


//given any node in list, search entire list
Node *searchlist(Node *h, void *info)
{
  Node* n = h;
  Node* after = h;
  Node* before = h->prev;

  //search all nodes after n (if any)
  while(after)
  {
    if (after->info == info)
    {
      return after;
    }
    after = after->next;
  }

  //search all nodes before n (if any)
  while(before)
  {
    if (before->info == info)
    {
      return n;
    }
    before = before->prev;
  }

  return NULL;
}

printing double linked list

//given any node in list, prints entire list
int printlist(Node *h)
{
  Node* t = h;

  //check we have any nodes before the node given
  while(t && t->prev)
  {
    t = t->prev;
  }

  while(t)
  {
    printf(" %d ", t->info);
    t = t->next;
  }
  printf(" NULL\n");
  return 0;
}

finally here is a routine which does find out broken links in double linked list, wondering what is a broken link…

 

double linked list - broken links

here is the code snippet for detecting broken links in double linked list…

int detecbrokentlist(Node *n)
{
  int brokenlinks = 0;
  Node *tmp = n;
  Node* after = n->next;
  Node* before = n->prev;

  //detect abnormalities in the list (broken links) after n (if any)
  while(after && tmp)
  {
    if ((after->prev != tmp) || (tmp->next != after))
    {
      brokenlinks++;
    }

    after = after->next;
    tmp = tmp->next;
  }

  //detect abnormalities in the list (broken links) before n (if any)
  tmp = n;
  while(before && tmp)
  {
    if ((before->next != tmp) || (tmp->prev != before))
    {
      brokenlinks++;
    }

    before = before->prev;
    tmp = tmp->prev;
  }

  return brokenlinks;
}

download full code for double linked list program [doublelinkedlist.c]