[C Data structures and Algorithms] Single Linked List (Circular Linked List)

  Hi~! We are here! I will let you know what about Linked List. Exactly Single Circular Linked List with C!

  Linked List is so simple and basic data structure. It has front, end node for expression start node and end node. And each nodes have data variable and next pointer variable. Next pointer variable has address next node. End node's next pointer variable point front node.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node {
 char *Name;
 struct _Node *Next;
} Node;

Node *front, *end; // head & tail
int currPos, listLength;

void initList(void);
int insertNode(char *);
int afterNode(char *,char *);
Node* findNode(char *);
Node* findNodeAt(int);
void printList(void);
int removeNode(char *);
void clearList(void);
int next();
int prev();
void setFront();
void setEnd();
Node* getNode();

  Above source code is ADT for a Single Linked List.

  There has to be struct for node. I made _Node struct with Name char pointer variable and Next _Node pinter variable. And define _Node to Node.

  Also made front,end currPos, listLength variables. Front and end is for list's start, end. CurrPos and ListLength is for list searcing.

  Here is realization source code.

#include "CList.h"


void initList(void) {
 front = (Node*)malloc(sizeof(Node));
 end = (Node*)malloc(sizeof(Node));
 front->Next = end;
 front->Name = "";
 end->Next = end;
 end->Name = "";
 currPos = 0;
 listLength = 0;
}

initList do initialization list. Do memory alllocate for front, end vars, and set to front's Next point end node, end's Next point front node. This time currPost has 0, listLength is 0.

int insertNode(char *Name) {
 Node *temp_node = (Node *)malloc(sizeof(Node));
 Node *position = front;
 temp_node->Name = Name;
 while(position->Next!=end) {
  position = position->Next;
 }
 temp_node->Next = position->Next;
 position->Next = temp_node;
 listLength++;
 return 1;
}

Function insertNode has Name argument. If you call insertNode with string. It make temp_node and set Name with string you sent. And temp_node's Next point end. After that last node's Next point temp_node.

And insertion some node between other nodes is same. If you want to insert C node between A,B. C's Next point B after that A's Next point C.

int afterNode(char *Name,char *targetName) {
 Node *temp_node = (Node *)malloc(sizeof(Node));
 Node *position = findNode(targetName);
 temp_node->Name = Name;
 
 if(position!=end) {
  temp_node->Next = position->Next;
  position->Next = temp_node;
  listLength++;
  return 1;
 }
 return -1;
}
Function afterNode has two arguments Name and targetName. It find the node has targetName and save into position var. And make a temp_node has Name arg. After that, insert temp_node after position.

Node* findNode(char *Name) {
 Node *start;

 for(start = front;start!=end;start=start->Next) {
  if(strcmp(start->Next->Name,Name)==0) {
   break;
  }
 }
 return start->Next;
}
Fucntion findNode search whole list and whether node is same Name with Name argument or not. If find node return that.

Node* findNodeAt(int indexAt) {
 Node *temp_node = front->Next;
 int index;
 for(index = 0;index<listLength&&temp_node!=end;index++) {
  if(index==indexAt) {
   return temp_node;
  }
  temp_node = temp_node->Next;

 }
 return NULL;
}
Function findNodeAt is similar with findNode. But it return node is at some index.

void printList(void) {
 Node *start;

 printf("%s","\n\n\nList Items\n");
 setFront();
 while((start=getNode())!=NULL&&next()) {
  printf("%s \n",start->Name);
 }
}
Function printList print out all list. In here call setFront function.

int removeNode(char *Name) {
 Node *start = front;
 Node *target;

 if((target=findNode(Name))!=start) {
  while(strcmp(start->Next->Name,Name)!=0) {
   start = start->Next;
  }
  start->Next = target->Next;
  free(target);
  listLength--;
  return 1;
 }
 return -1;
}
Function remove is simple too. find target node and arrange Next pointer. And do memory free.

Arranging Next pointer A node point C, after that clean up B.

void clearList(void) {
 Node *start = front->Next;
 Node *next = start->Next;

 while(next!=end) {
  free(start);
  start = next;
  next = next->Next;
 }

 free(front);
 free(end);
 initList();
}
Function clearList is do memory clean up and call initList function.

Here is next, prev, setFront, setEnd function. These are for changing list position.

int next() {
 if(currPos < listLength) {
  currPos++;
  return currPos;
 }
 return -1;
}

int prev() {
 if(currPos > 0) {
  currPos--;
  return currPos;
 }
 return -1;
}

void setFront() {
 currPos = 0;
}

void setEnd() {
 currPos  = listLength-1;
}

Node* getNode() {
 return findNodeAt(currPos);
}

List is basic data structure. If you want to learn another data structure or algorithms? You have to know List and Pointer. I hope it easy to you. Next posting is Doubly Linked List.

* If you run this program use this main function.

#include "CList.h"

int main() {
 Node* temp;

 initList();

 printf("%s","List Test Program\n");

 insertNode("Jake Song");
 insertNode("Alex Song");
 insertNode("Minhee Kim");

 printList();
 
 removeNode("Alex Song");


 printList();
 clearList();
 printList();
 
  return 0;
}