hi guys. I am trying to implement a circular singly linked list to use it for a project i have. but i was not able to do it. i will post the code i've written. Please if anyone has an experience with this topic reply to my message as soon as possible.

****************
HERE IS MY CODE
****************

typedef struct linked_list
{
void *message;//to store message items
int boxSize;//defines the number of elements in the list
struct linked_list *next;//to point to next element in the list
}mailbox_t;//name of list to be created


mailbox_t *create_mailbox (int mailbox_size)
{
mailbox_t *mb,*head;
int i;

head=NULL;

for(i=0;i<mailbox_size;i++)
{
mb = (mailbox_t *) malloc(sizeof(mailbox_t));
mb -> next = head;
head = mb;
}

mb->boxSize=mailbox_size;

if(mb==NULL)
return NULL;

return mb;

}// end of function
********************* END OF CODE *********************************

the code above is for singly linked list and it is not circular. Can anyone modify this code such that it becomes circular singly linked list.

Thanks in advance

Abdul Hameed

the concept is, the "next" field of the last element in a singly non-circular linked list should be NULL. to make it circular, it should be point to the first element of the list.

now make the modification yourself.

---

~Donotalo()

: the concept is, the "next" field of the last element in a singly non-circular linked list should be NULL. to make it circular, it should be point to the first element of the list.
:
: now make the modification yourself.
:
:

---

~Donotalo()
:
:

Why would anyone want to have a circular linked list?

As I see it it would only make the code more complex and less efficient.

: Why would anyone want to have a circular linked list?
:
: As I see it it would only make the code more complex and less efficient.
:
may be this is part of an assignment? not bad though.

---

~Donotalo()

: : Why would anyone want to have a circular linked list?
: :
: : As I see it it would only make the code more complex and less efficient.
: :
: may be this is part of an assignment? not bad though.
:
:

---

~Donotalo()
:
:

As Mr. Donotalo stated " this is part of an assignment? ". I have an operating systems course and i am supposed to do all coding with C. In this assignment i must use linked lists.

Anyway thanx for your help guys

Best Regards
Abdul Hameed

: : : Why would anyone want to have a circular linked list?
: : :
: : : As I see it it would only make the code more complex and less efficient.
: : :
: : may be this is part of an assignment? not bad though.
: :
: :

---

~Donotalo()
: :
: :
:
: As Mr. Donotalo stated " this is part of an assignment? ". I have an operating systems course and i am supposed to do all coding with C. In this assignment i must use linked lists.
:
: Anyway thanx for your help guys
:
: Best Regards
: Abdul Hameed
:

But that doesn't explain why you should use a circular list, it's just plain ineffiecient and dumb.
There're no benefit of using a circular list instead of a plain linked list.

So why are you using such a dumb design in an OS then?

: : : : Why would anyone want to have a circular linked list?
: : : :
: : : : As I see it it would only make the code more complex and less efficient.
: : : :
: : : may be this is part of an assignment? not bad though.
: : :
: : :

---

~Donotalo()
: : :
: : :
: :
: : As Mr. Donotalo stated " this is part of an assignment? ". I have an operating systems course and i am supposed to do all coding with C. In this assignment i must use linked lists.
: :
: : Anyway thanx for your help guys
: :
: : Best Regards
: : Abdul Hameed
: :
:
: But that doesn't explain why you should use a circular list, it's just plain ineffiecient and dumb.
: There're no benefit of using a circular list instead of a plain linked list.
:
: So why are you using such a dumb design in an OS then?
:

In this assignment we have the choice for chosing any data structure we prefer. I said that CSLL might be helpful and easier to dear with, but I think I will use only plain SLL instead of CSLL. The following is the assignment doc.
***********************************************

Project Title:
Mailbox Abstraction Library

Project Objective:
- To demonstrate your understanding of Thread Creation and Execution concept.
- To demonstrate your understanding of Thread synchronization
- (Optionally) How to compile my project using make utility.

********* The Assignment *******************
This assignment is to be written in the C programming language. You will implement a mailbox abstraction that has the following functions (see below). You should define a mailbox type (mailbox_t) and pass it as the first parameter to each of the functions. The prototypes for the mailbox abstraction are as follows:

mailbox_t * create_mailbox (int mailbox_size)
Allocate and initialize a new mailbox that can hold at most mailbox_size.

void put_message (mailbox_t *mb, void *item) Add item to the end of the mailbox. If the mailbox queue already contains mailbox_size, the put operation should block the calling thread until there is room in the mailbox.

void *get_message (mailbox_t *mb)
Remove the first item from the mailbox and return that item. If the mailbox is empty, the calling thread shou!ld block.

void *read_head(mailbox_t *mb)
Return head of mailbox without removing the item. This function should return NULL if the queue is empty.

int probe (mailbox_t *mb)
Test if the mailbox contains an item. It will return true if the mailbox is not empty.
Implementation Requirements
The entire implementation should be in the file mailbox.c. You may NOT change the existing functions parameters or return types. A header file named mailbox.h is required to declare the mailboxs type and all the function prototypes.

You also have to write a test program named testmail.c that contains the main function. The test program that you write should create two new threads and one mailbox. The first thread should put the numbers 1..10 into the mailbox queue, and the second thread should remove the items and print them out as they are removed. When you create the mailbox, it should have a maximum of 5 items. You should also test other features of your program. When we test your program, we will substitute our own version of testmail.c with additional test cases.

*********************************************************

Regards

: the concept is, the "next" field of the last element in a singly non-circular linked list should be NULL. to make it circular, it should be point to the first element of the list.
:
: now make the modification yourself.
:
:

---

~Donotalo()
:
:

i have modified the code so it becomes a circular linked list, but i have a problem with insertion and deletion. whenever i remove an item and insert another one instead of that item, the last item will not be retrieved, i,e if list contains 1,2,3,4,5 if i remove 1 then it becomes 2,3,4,5 then if i insert 6 it should become 6,2,3,4,5 with 2 is the head. the problem is that my code will not retrieve 5 instead it will retrieve 6 and ignore 5. i will post my code so you can check it please if you find any error reply to this message.

here is the code i wrote
****************************
//this create the circular list
mailbox_t *create_mailbox (int mailbox_size)
{
mailbox_t *mb;
int i;

head = tail = NULL;
for(i=1;i<=mailbox_size;i++)
{
mb = (mailbox_t *) malloc(sizeof(mailbox_t));//allocate memory
//tail -> next = head;
mb -> next = head;
head = mb;
if(i==1)
tail = mb;
if(i==mailbox_size)
tail -> next = head;
}

mb->boxSize=mailbox_size;
//tail = fnode = mb;
curr=head;
if(mb==NULL)
return NULL;

return mb;

}

//this inserts to the list
void put_message (mailbox_t *mb, void *item)
{
int i;//used to count size of box to check if it is full or not
i=1;

if( head -> message == NULL)
{
//tail = fnode = head;
head -> message = tail -> message = mb -> message = curr -> message = item;
//head = tail = fnode = mb;
availSize++;
printf("PUT: CON 1 *** %s ***\n",(char *) head -> message);
}

else
{
while( mb -> next != head && mb -> message )
{
mb = mb -> next;
i++;
}
//printf("PUT: CON 2 *** %s ***\n",(char *) item);
tail -> message = mb -> message = item;
//tail = mb;
availSize++;
printf("PUT: CON 2 *** %s ***\n",(char *) tail -> message);
}
int j;
j=availSize;
printf("AVSize: %d\n",j);

}

//finally this removes item from the list

void *get_message (mailbox_t *mb)
{
void *mess;
int i;
//printf("GET: CON 1 *** %s ***\n",(char *) head->message);
if(mb -> message != NULL)
{
mess = mb -> message;
head -> message = mb -> message = curr -> message = NULL;

if( mb -> next != NULL
*mb = *head = *head -> next;
else
*mb = *head = *curr;

printf("GET: CON 1 *** %s ***\n",(char *) mess);
availSize--;
}
printf("AVSize: %d\n",availSize);
}

*************************************************
please write your comments about this code.

Regards

Abdul Hameed

It seems to me that what you have made is not a circular list, but rather an array with slots that can be empty.

A circular linked list would look like this and does have some funny benefits over other lists (notably that you can search forward from any posistion in the list without worrying about the "end of list" condition).

I had a bash of an implementation. Might be flawed, but I am sure that you will see the difference between your array implementation and a list.

typedef struct ListElement_tag
{
	struct ListElement_tag* ptNext;
	void* pvData;
}ListElementT;

typedef struct CircularList_tag
{
	ListElementT* ptHead;
	int cnElements;
}CircularListT;

CircularListT* CircularList_Create()
{
	CircularListT* ptList;
	
	ptList = malloc(sizeof(CircularListT));
	
	ptList->cnElements = 0;
	ptList->ptHead = NULL;
	
	return ptList;
}


void CircularList_Destroy(CircularListT* ptList)
{	
	free(ptList);
}

ListElementT* CircularList_GetTail(CircularList* ptList)
{
	ListElementT* ptCurrent = ptList->pHead;
	ListElementT* ptNext;
	
	while (ptCurrent != NULL)
	{
		ptNext = ptCurrent->ptNext;
		if (ptNext == ptList->ptHead)
		{
			/* The current element is the tail (since its next element is the list head). */
			return ptCurrent;
		}
	}
	
	return NULL;
}

void CircularList_InsertTail(CircularListT*ptList, void* pvData)
{
	ListElementT* ptTail;
	ListElementT* ptNewElement = malloc(sizeof(ListElementT));
	
	ptNewElement->pvData = pvData;
	
	ptTail = CircularList_GetTail(ptList);
	if (ptTail != NULL)
	{
		/* Let the tail point to the new element (rather than the head). */
		ptTail->ptNext = ptNewElement;
	}
	else
	{
		/* List is empty, create head. */
		ptList->ptHead = ptNewElement;
	}
	
	/* The new element is the tail and must point to the head as its next element. */
	ptNewElement->ptNext = ptList->ptHead;
	
	ptList->cnElements++;
}

ListElementT* ListElement_GetElementAtPos(ListElementT* ptElement, int pos)
{	
	while (pos > 0)
	{
		ptElement = ptElement->ptNext;
		pos--;
	}
	return ptElement;
}

/* Remove an element from a circular list. */
void CircularList_RemoveElement(CircularListT* ptList, ListElementT* ptElement)
{
	ListElement* ptNext = ptElement->ptNext;
	ListElement* ptPrevious = ListElement_GetElementAtPos(ptElement, ptList->cnElements - 1);
	
	ptPrevious->ptNext = ptNext;
	
	if (ptList->ptHead == ptElement)
	{
		/* The element to remove is the head. Promote the next element to the head. */
		ptList->ptHead = ptNext;
	}
	
	/* Now remove the element. */
	free(ptElement);
	ptList->cnElements--;
	
	/* Special case: If list is empty, the head should be removed. */
	ptList->ptHead = NULL;
}

When searching the list, the best way to go around it is probably:
1. Start at the head.
2. Use a for loop (counting to cnElements).

Hope this helps.

:
: When searching the list, the best way to go around it is probably:
: 1. Start at the head.
: 2. Use a for loop (counting to cnElements).
:

Why not?:

search(list){
    a = list
    do{
        //do stuff
    }while(a!=(list=list.next))
}

: Why not?:

: search(list){
:     a = list
:     do{
:         //do stuff
:     }while(a!=(list=list.next))
: }

That would work too.

For clarity, I'd prefer:

search(ListElement* ptStart){
    ListElement* ptNext = ptStart;

    for (;;)
    {
        //do stuff
        ptNext = ptNext.next;

        if (ptNext == ptStart)
        {
            /* Reached beginning. Nothing found. */
            return;
        }
    }
}

Thank you dear friend your code helped me a lot. I really appreciate your help. Now I am left with few things in this project.

Best Regards


: It seems to me that what you have made is not a circular list, but rather an array with slots that can be empty.
:
: A circular linked list would look like this and does have some funny benefits over other lists (notably that you can search forward from any posistion in the list without worrying about the "end of list" condition).
:
: I had a bash of an implementation. Might be flawed, but I am sure that you will see the difference between your array implementation and a list.
:
:

: typedef struct ListElement_tag
: {
: 	struct ListElement_tag* ptNext;
: 	void* pvData;
: }ListElementT;
: 
: typedef struct CircularList_tag
: {
: 	ListElementT* ptHead;
: 	int cnElements;
: }CircularListT;
: 
: CircularListT* CircularList_Create()
: {
: 	CircularListT* ptList;
: 	
: 	ptList = malloc(sizeof(CircularListT));
: 	
: 	ptList->cnElements = 0;
: 	ptList->ptHead = NULL;
: 	
: 	return ptList;
: }
: 
: 
: void CircularList_Destroy(CircularListT* ptList)
: {	
: 	free(ptList);
: }
: 
: ListElementT* CircularList_GetTail(CircularList* ptList)
: {
: 	ListElementT* ptCurrent = ptList->pHead;
: 	ListElementT* ptNext;
: 	
: 	while (ptCurrent != NULL)
: 	{
: 		ptNext = ptCurrent->ptNext;
: 		if (ptNext == ptList->ptHead)
: 		{
: 			/* The current element is the tail (since its next element is the list head). */
: 			return ptCurrent;
: 		}
: 	}
: 	
: 	return NULL;
: }
: 
: void CircularList_InsertTail(CircularListT*ptList, void* pvData)
: {
: 	ListElementT* ptTail;
: 	ListElementT* ptNewElement = malloc(sizeof(ListElementT));
: 	
: 	ptNewElement->pvData = pvData;
: 	
: 	ptTail = CircularList_GetTail(ptList);
: 	if (ptTail != NULL)
: 	{
: 		/* Let the tail point to the new element (rather than the head). */
: 		ptTail->ptNext = ptNewElement;
: 	}
: 	else
: 	{
: 		/* List is empty, create head. */
: 		ptList->ptHead = ptNewElement;
: 	}
: 	
: 	/* The new element is the tail and must point to the head as its next element. */
: 	ptNewElement->ptNext = ptList->ptHead;
: 	
: 	ptList->cnElements++;
: }
: 
: ListElementT* ListElement_GetElementAtPos(ListElementT* ptElement, int pos)
: {	
: 	while (pos > 0)
: 	{
: 		ptElement = ptElement->ptNext;
: 		pos--;
: 	}
: 	return ptElement;
: }
: 
: /* Remove an element from a circular list. */
: void CircularList_RemoveElement(CircularListT* ptList, ListElementT* ptElement)
: {
: 	ListElement* ptNext = ptElement->ptNext;
: 	ListElement* ptPrevious = ListElement_GetElementAtPos(ptElement, ptList->cnElements - 1);
: 	
: 	ptPrevious->ptNext = ptNext;
: 	
: 	if (ptList->ptHead == ptElement)
: 	{
: 		/* The element to remove is the head. Promote the next element to the head. */
: 		ptList->ptHead = ptNext;
: 	}
: 	
: 	/* Now remove the element. */
: 	free(ptElement);
: 	ptList->cnElements--;
: 	
: 	/* Special case: If list is empty, the head should be removed. */
: 	ptList->ptHead = NULL;
: }
: 

:
: When searching the list, the best way to go around it is probably:
: 1. Start at the head.
: 2. Use a for loop (counting to cnElements).
:
: Hope this helps.
: