Fluffy Stuff

A tmp place to rest

Generate a Linked List from a given array

Perface

Well, I'm starting to work through Data Structures and Algorithm Analysis in C (2nd edition) (referenced as MAW in the following posts) a couple of months agao to serve several purposes:

  • to get enough familarity with C programming language
  • to keep my computer science foundation knowledge fresh
  • I'm interested in System-level programming and mastering C and C++ is a must.

I work on DB2 codebase but I don't play around the material I mentioned above a lot. Things can get rusty pretty quickly. So, I need a way to keep fresh.

Important

All the source code relates to this book can be found on my git repo

Solution

For completeness and readability, here is my basic node declaraiton and definition.

typedef int ET; // ET shorts for "ElementType"

// we always assume there is a dummy node at the very beginning
// of the list.
#ifndef _LINKED_LIST_H
#define _LINKED_LIST_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Pos;

#endif

// placed in the implementation file
struct Node
{
  ET Element;
  Pos Next;
};

When I try to work through the linked list related questions in Chapter 2, the first thing I need to do is to able to verify my solution. I need to figure out a way to quickly generate a test linked list. So, that's what List initializeList(ET A[], int arrayLen); for.

static List
initializeNoHeaderList(ET A[], int arrayLen)
{
  int i = 0;
  Pos tmpNode;;

  if (arrayLen == 0)
  {
    return NULL;
  }
  tmpNode = malloc(sizeof(struct Node));
  if (tmpNode == NULL)
  {
    exit(EXIT_FAILURE);
  }
  tmpNode->Element = A[i];
  tmpNode->Next = initializeNoHeaderList(A+1, arrayLen-1);
  return tmpNode;
}

List
initializeList(ET A[], int arrayLen)
{
  Pos header;

  header = malloc(sizeof(struct Node));
  if (header == NULL)
  {
    exit(EXIT_FAILURE);
  }
  header->Next = initializeNoHeaderList(A, arrayLen);
  return header;
}

initializeList adds a dummy node and invokes initializeNoHeaderList to actually generate linked list from a given array. Inside initializeNoHeaderList, we use recursion to generate the list from array.

Note

If we actually change tmpNode->Next = initializeNoHeaderList(A+1, arrayLen-1); to tmpNode->Next = initializeList(A+1, arrayLen-1);, this can lead to a list contains nodes alternate between actual data node and the dummy node. (i.e. ET test_arr[] = {23, 44, 45, 57, 89, -1}; then the generated linked list will be 23->0->44->0->45->0->57->0->89->0->-1->0->)

comments powered by Disqus