Advanced Data Structures

• In the previous section, we mentioned that you can create pointers to structures. The Data Structures presented here all require pointers to structs, or more specifically they are self-referential structures.
• These self-referential structures contain pointers within the structs that refer to another identical structure.

Advanced Data Structures :: Linked Lists

• Linked lists are the most basic self-referential structures. Linked lists allow you to have a chain of structs with related data.
• So how would you go about declaring a linked list? It would involve a struct and a pointer:

    struct llnode {
      <type> data;
      struct llnode *next;
    };
  

  The <type> signifies data of any type. This is typically a pointer to something, usually another struct. The next line is the next pointer to another llnode struct. Another more convenient way using typedef:

    typedef struct list_node {
      <type> data;
      struct list_node *next;
    } llnode;
  
    llnode *head = NULL;
  

  Note that even the typedef is specified, the next pointer within the struct must still have the struct tag!
• There are two ways to create the root node of the linked list. One method is to create a head pointer and the other way is to create a dummy node. It's usually easier to create a head pointer.
• Now that we have a node declaration down, how do we add or remove from our linked list? Simple! Create functions to do additions, removals, and traversals.
  • Additions: A sample Linked list addition function:

      void add(llnode **head, <type> data_in) {
        llnode *tmp;
    
        if ((tmp = malloc(sizeof(*tmp))) == NULL) {
          ERR_MSG(malloc);
          (void)exit(EXIT_FAILURE);
        }
        tmp->data = data_in;
        tmp->next = *head;
        *head = tmp;
      }
    
      /* ... inside some function ... */
      llnode *head = NULL;
      <type> *some_data;
      /* ... initialize some_data ... */
    
      add(&head, some_data);
    

    What's happening here? We created a head pointer, and then sent the address-of the head pointer into the add function which is expecting a pointer to a pointer. We send in the address-of head. Inside add, a tmp pointer is allocated on the heap. The data pointer on tmp is moved to point to the data_in. The next pointer is moved to point to the head pointer (*head). Then the head pointer is moved to point to tmp. Thus we have added to the beginning of the list.
  • Removals: You traverse the list, querying the next struct in the list for the target. If you get a match, set the current target next's pointer to the pointer of the next pointer of the target. Don't forget to free the node you are removing (or you'll get a memory leak)! You need to take into consideration if the target is the first node in the list. There are many ways to do this (i.e. recursively). Think about it!
  • Traversals: Traversing list is simple, just query the data part of the node for pertinent information as you move from next to next. There are different methods for traversing trees (see Trees).
• What about freeing the whole list? You can't just free the head pointer! You have to free the list. A sample function to free a complete list:

    void freelist(llnode *head) {
      llnode *tmp;
  
      while (head != NULL) {
        free(head->data);     /* Don't forget to free memory within the list! */
        tmp = head->next;
        free(head);
        head = tmp;
      }
    }
  

  Now we can rest easy at night because we won't have memory leaks in our lists!

Advanced Data Structures :: Stacks

• Stacks are a specific kind of linked list. They are referred to as LIFO or Last In First Out.
• Stacks have specific adds and removes called push and pop. Pushing nodes onto stacks is easily done by adding to the front of the list. Popping is simply removing from the front of the list.
• It would be wise to give return values when pushing and popping from stacks. For example, pop can return the struct that was popped.

Advanced Data Structures :: Queues

• Queues are FIFO or First In First Out. Think of a typical (non-priority) printer queue: The first jobs submitted are printed before jobs that are submitted after them.
• Queues aren't more difficult to implement than stacks. By creating a tail pointer you can keep track of both the front and the tail ends of the list.
• This allows you to enqueue onto the tail of the list, and dequeue from the front of the list.

Advanced Data Structures :: Hash Tables

• So what's the problem with linked lists? Their efficiency isn't that great. (In Big-O notation, a linked list performs O(n)). Is there a way to speed up data structures?
• Enter hash tables. Hash tables provide O(1) performance while having the ability to grow dynamically. The key to a well-performing hash table is understanding the data that will be inserted into it. By custom tailoring an array of pointers, you can have O(1) access.
• But you are asking, how do you know where a certain data piece is in within the array? This is accomplished through a key. A key is based off the data, the most simple one's involve applying a modulus to a certain piece of information within the data. The general rule, is that if a key sucks, the hash table sucks.
• What about collisions (e.g. same key for two different pieces of information)? There are many ways to resolve this, but the most popular way is through coalesced chaining. You can create a linked list from the array position to hold multiple data pieces, if necessary.
• Weiss provides a more in-depth study on hash tables, section 10.3, pg. 271-279.

Advanced Data Structures :: Trees

• Another variation of a linked list is a tree. A simple binary tree involves having two types of "next" pointers, a left and a right pointer. You can halve your access times by splitting your data into two different paths, while keeping a uniform data structure. But trees can degrade into linked list efficiency.
• There are different types of trees, some popular ones are self-balancing. AVL trees are a typical type of tree that can move nodes around so that the tree is balanced without a >1 height difference between levels.
• If you want more information on trees or self-balancing trees, you can query google about this.

Advanced Data Structures Review

• Linked lists, stacks, queues, hash tables, trees are all different types of data structures that can help accomodate almost any type of data.
• Other data structures exist such as graphs. That is beyond the scope of this tutorial.
• If you want a more in-depth look at the data structures discussed here, refer to Weiss chapter 10, pg. 257-291 and chapter 11 pg. 311-318 for information on binary search trees.
• For more information on recursive functions, see Weiss chapter 11, pg. 294-311.

Notice: Please do not replicate or copy these pages and host them elsewhere. This is to ensure that the latest version can always be found here.

Disclaimer: The document author has published these pages with the hope that it may be useful to others. However, the document author does not guarantee that all information contained on these webpages are correct or accurate. There is no warranty, expressed or implied, of merchantability or fitness for any purpose. The author does not assume any liability or responsibility for the use of the information contained on these webpages.

If you see an error, please send an email to the address below indicating the error. Your feedback is greatly appreciated and will help to continually improve these pages.

© 1999-2024 Alfred Park (fred [ANTISPAM-REMOVE-THIS] AT randu.org)