Skip to content

Instantly share code, notes, and snippets.

@ksvbka

ksvbka/linkedList.c

Created October 2, 2015 07:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ksvbka/47697ebe5f9aedacc477 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ksvbka/47697ebe5f9aedacc477 to your computer and use it in GitHub Desktop.
Download ZIP
Library for Linkedlist data struct
Raw
linkedList.c
/********************************************************************************
Product : Linkedlist Library
Module :
Author : Trung Kien - [email protected]
Description : Library for Linkedlist data struct.
********************************************************************************/
/*-----------------------------------------------------------------------------*/
/* Header inclusions */
/*-----------------------------------------------------------------------------*/
#include "stdio.h"
#include "stdlib.h"
#include "linkedlist.h"
#include "assert.h"
/*-----------------------------------------------------------------------------*/
/* Local Constant definitions */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Local Macro definitions */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Local Data type definitions */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Global variables */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Function prototypes */
/*-----------------------------------------------------------------------------*/
listNode Node_create(item data);
int Node_delete(listNode* pList);
int ListNode_push(listNode* pList, item data);
int ListNode_insertBegin(listNode *pList, item data);
int ListNode_insertEnd(listNode *pList, item data);
int ListNode_insertMid(listNode *pList, item data, int position);
int ListNode_removeBegin(listNode* pList);
int ListNode_removeLast(listNode* pList);
int ListNode_removeMid(listNode* pList, int position);
int ListNode_show(listNode pList);
int ListNode_length(listNode pList);
int ListNode_count(listNode pList, item pattern);
int ListNode_getNth(listNode plist, int position, int *value);
int ListNode_delete(listNode *pList);
int ListNode_sorftedInsert(listNode *pList, item data);
int ListNode_insertSoft(listNode *pList);
int ListNode_append(listNode *a, listNode *b);
int ListNode_frontBackSplit(listNode source, listNode* frontRef, listNode* backRef);
int ListNode_moveNode(listNode *destRef, listNode *sourceRef);
int ListNode_alternatingSplit(listNode source, listNode* EventRef, listNode* OddRef);
listNode ListNode_shuffleMerge(listNode a, listNode b);
int ListNode_mergeSoft(listNode* sourceRef);
listNode ListNode_sortedIntersect(listNode a, listNode b);
int ListNode_reverse(listNode* sourceRef);
// int ListNode_update(listNode *pList, int position);
// int ListNode_search(listNode *pList, item data);
/*-----------------------------------------------------------------------------*/
/* Function implementations */
/*-----------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------------
function : ListNode_create
Purpose : Create and allocation memmory for a new listNode
Parameters : VOID
Return : 0 if success, -1 if failt.
--------------------------------------------------------------------------------*/
listNode Node_create(item data)
{
listNode p;
p = (listNode)malloc(sizeof(node));
if(p != NULL)
{
p->next = NULL;
p->data = data;
}
return p;
}
/*--------------------------------------------------------------------------------
function : Node_delete
Purpose : Delete and free memory for a listNode
Parameters : listNode* pList
Return : 0 if success, -1 if failt
--------------------------------------------------------------------------------*/
int Node_delete(listNode* pList)
{
*pList = NULL;
return 0;
}
/*--------------------------------------------------------------------------------
function : ListNode_insertBegin
Purpose : Insert an element to the begin of listNode
Parameters : listNode * pList, item data
Return : positon of element if success or -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_insertBegin(listNode *pList, item data)
{
listNode p = Node_create(data);
if(p == NULL )
return -1;
else
{
p->next = *pList;
*pList = p;
return 0;
}
return -1;
}
/*--------------------------------------------------------------------------------
function : ListNode_insertEnd
Purpose : Insert an element to the end of listNode
Parameters : listNode * pList, item data
Return : positon of element if success or -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_insertEnd(listNode *pList, item data)
{
listNode p = Node_create(data);
if(p == NULL)
return -1;
if(*pList == NULL)
*pList = p;
else
{
listNode r = *pList;
while(r->next != NULL)
r = r->next;
r->next = p;
return 0;
}
return -1;
}
/*--------------------------------------------------------------------------------
function : ListNode_insertMid
Purpose : Insert an element to the middle of listNode
Parameters : listNode * pList, item data, int position
Return : positon of element if success or -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_insertMid(listNode *pList, item data, int position)
{
/*Check input*/
if(position < 0)
return -1;
if(position == 0)
{
ListNode_insertBegin(pList, data);
return 0;
}
int nIndex = 0;
listNode p = *pList;
while(p != NULL)
{
if(nIndex == position -1)
{
listNode r = Node_create(data);
r->next = p->next;
p->next = r;
return nIndex;
}
p = p->next;
nIndex++;
}
return -1;
}
/*--------------------------------------------------------------------------------
function : ListNode_removeBegin
Purpose : Remove an begin element of listNode
Parameters : listNode * pList, item data
Return : positon of element if success or -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_removeBegin(listNode* pList)
{
if(*pList == NULL)
return -1;
else
{
listNode r = *pList;
*pList = r->next;
Node_delete(&r);
return 0;
}
return -1;
}
/*--------------------------------------------------------------------------------
function : ListNode_removeLast
Purpose : Remove the last element of listNode
Parameters : listNode * pList
Return : positon of element if success or -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_removeLast(listNode *pList)
{
listNode p = *pList;
if(p == NULL) return -1;
if(p->next == NULL)
{
ListNode_removeBegin(&p);
return 0;
}
listNode r = p;
while(r->next->next != NULL)
{
r = r->next;
}
r->next = NULL;
return 0;
}
/*--------------------------------------------------------------------------------
function : ListNode_removeMid
Purpose : Remove the middle element of listNode
Parameters : listNode * pList, item data, int position
Return : positon of element if success or -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_removeMid(listNode* pList, int position)
{
int nIndex = 1;
listNode p = *pList;
if(p == NULL)
return -1;
if(position == 0)
{
ListNode_removeBegin(pList);
return 0;
}
while(p != NULL)
{
if(nIndex == position)
{
listNode q = p->next;
p->next = q->next;
q->next = NULL;
free(q);
return 0;
}
nIndex++;
p = p->next;
}
return -1;
}
/*--------------------------------------------------------------------------------
function : ListNode_show
Purpose : Show the data of ListNode
Parameters : ListNode pList
Return : 0 if succsess, -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_show(listNode pList)
{
while(pList != NULL)
{
printf("%d\t", pList->data);
pList = pList->next;
}
printf("\n");
return 0;
}
// Tra ve chieu dai cua list
int ListNode_length(listNode pList)
{
int count = 0;
while(pList != NULL)
{
count++;
pList = pList->next;
}
return count;
}
/*--------------------------------------------------------------------------------
function : ListNode_count
Purpose : count the number of occurrences of pattern in a list
Parameters : listNode pList, item Pattern
Return : count
--------------------------------------------------------------------------------*/
int ListNode_count(listNode pList, item pattern)
{
int count = 0;
while(pList != NULL)
{
if(pList->data == pattern) count++;
pList = pList ->next;
}
return count;
}
/*--------------------------------------------------------------------------------
function : ListNode_getNth
Purpose : returns the data value stored in the node at that index position
Parameters : listNode pList, int position, int *value
Return : nIndex or -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_getNth(listNode pList, int position, int *value)
{
int nIndex = 0;
while(pList != NULL)
{
if(nIndex == position)
{
*value = pList->data;
return nIndex;
}
pList = pList->next;
nIndex++;
}
return -1;
}
/*--------------------------------------------------------------------------------
function : ListNode_delete
Purpose : Deallocates all of its memory and sets itshead pointer to NULL (the empty list).
Parameters : ListNode *pList
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_delete(listNode *pList)
{
listNode current = *pList;
listNode next;
while(current != NULL)
{
next = current->next;
free(current);
current = next;
}
*pList = NULL;
return 0;
}
/*--------------------------------------------------------------------------------
function : ListNode_push
Purpose : Push data to the begin of List (NOTE: canbe used as push(&(current->next), data))
Parameters : ListNode* pList, item data
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_push(listNode* pList, item data)
{
listNode p = Node_create(data);
p->next = *pList;
*pList = p;
return 0;
}
/*--------------------------------------------------------------------------------
function : ListNode_sorftInsert
Purpose : Inserts the node into the correct sorted position in the list (List sorted in incresing order)
Parameters : listNode *pList, item data
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_sorftedInsert(listNode *pList, item data)
{
listNode current = *pList;
int count = 0;
while(current != NULL)
{
if(data < current->data)
break;
count++;
current = current->next;
}
ListNode_insertMid(pList, data,count);
return 0;
}
/*--------------------------------------------------------------------------------
function : ListNode_insertSoft
Purpose : Rearranges its nodes so they are sorted in increasing order.
It should use SortedInsert().
Parameters : listNode *pList
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_insertSoft(listNode *pList)
{
listNode newList = NULL;
listNode current = *pList;
while(current != NULL)
{
ListNode_sorftedInsert(&newList, current->data);
current = current->next;
}
*pList = newList;
return 0;
}
/*--------------------------------------------------------------------------------
function : ListNode_append
Purpose : Appends list'b' onto the end of list'a'
Parameters : listNode *a, listNode *b
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_append(listNode *a, listNode *b)
{
if(*a == NULL)
{
*a = *b;
}
else
{
listNode current = *a;
while(current->next != NULL)
current = current->next;
current->next = *b;
}
*b = NULL;
return 0;
}
/*--------------------------------------------------------------------------------
function : ListNode_frontBackSplit
Purpose : Split a list into two sublists — one for the front half, and one for the back half
Parameters : listNode source, listNode* frontRef, listNode* backRef
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_frontBackSplit(listNode source, listNode* frontRef, listNode* backRef)
{
int sourceLength = ListNode_length(source);
if(sourceLength == 0)
{
*frontRef = NULL;
*backRef = NULL;
return 0;
}
if(sourceLength == 1)
{
*frontRef = source;
*backRef = NULL;
return 1;
}
int half = (sourceLength % 2 == 0 ? (sourceLength/2) : (sourceLength/2 +1));
int i;
*frontRef = source;
listNode endOfFront = source;
for(i = 1; i < half ; i++)
endOfFront = endOfFront->next;
*backRef = endOfFront->next;
endOfFront->next = NULL;
return i;
}
/*--------------------------------------------------------------------------------
function : ListNode_removeDuplicates
Purpose : Remove any duplicates in a list sorted in increasing order
Parameters : listNode *pList
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_removeDuplicates(listNode *pList)
{
if(*pList == NULL || (*pList)->next == NULL)
return 0;
listNode current = *pList;
listNode next = current->next;
while(next!= NULL)
{
if(current->data == next->data)
{
next = next->next;
current->next = next;
}
else
{
next = next->next;
current = current->next;
}
}
return 0;
}
/*
*/
/*--------------------------------------------------------------------------------
function : ListNode_moveNode
Purpose : Take the node from the front of the source, and move it to the front of the dest.
It is an error to call this with the source list empty.
Parameters : listNode *destRef, listNode *sourceRef
Return : 0 if success, -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_moveNode(listNode *destRef, listNode *sourceRef)
{
if(*sourceRef != NULL)
{
ListNode_insertBegin(destRef, (*sourceRef)->data);
ListNode_removeBegin(sourceRef);
return 0;
}
// if(*sourceRef == NULL)
// return -1;
// else
// {
// listNode current = *sourceRef;
// *sourceRef = (*sourceRef)->next;
// current->next = *destRef;
// *destRef = current;
// return 0;
// }
return -1;
}
/*--------------------------------------------------------------------------------
function : ListNode_alternatingSplit
Purpose : Given the source list, split its nodes into two shorter lists.
If we number the elements 0, 1, 2, ... then all the even elements
should go in the first list, and all the odd elements in the second.
The elements in the new lists may be in any order.
Parameters : listNode source, listNode* EventRef, listNode* OddRef
Return : 0 if success, -1 if failt
--------------------------------------------------------------------------------*/
int ListNode_alternatingSplit(listNode source, listNode* EventRef, listNode* OddRef)
{
listNode current = source;
while(current!= NULL)
{
if(current->data < 0)
return -1;
else
{
current->data %2 == 0 ? ListNode_moveNode(EventRef, &current) : ListNode_moveNode(OddRef, &current);
}
}
return 0;
}
/*
Merge the nodes of the two lists into a single list taking a node
alternately from each list, and return the new list.
*/
/*--------------------------------------------------------------------------------
function : ListNode_shuffleMerge
Purpose : Merge the nodes of the two lists into a single list taking a node
alternately from each list, and return the new list.
Parameters : listNode a, listNode b
Return : listNode
--------------------------------------------------------------------------------*/
listNode ListNode_shuffleMerge(listNode a, listNode b)
{
if(a == NULL)
return b;
if(b == NULL)
return a;
listNode currentA = a;
listNode currentB = b;
listNode pList = NULL;
int count = 0;
while((currentA != NULL) || (currentB != NULL))
{
if((count % 2 == 0 ) && currentA !=NULL)
{
ListNode_insertEnd(&pList, currentA->data);
currentA = currentA->next;
}
if((count % 2 != 0) && currentB != NULL)
{
ListNode_insertEnd(&pList, currentB->data);
currentB = currentB->next;
}
count++;
}
return pList;
}
/*--------------------------------------------------------------------------------
function : ListNode_mergeSoft
Purpose : Sort the list by using merge soft algorithm
Parameters : listNode* sourceRef
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_mergeSoft(listNode* sourceRef)
{
;
}
/*--------------------------------------------------------------------------------
function : ListNode_sortedIntersect
Purpose : listNode a, listNode b
Parameters : Compute a new sorted list that represents the intersection
of the two given sorted lists.
Return : pList
--------------------------------------------------------------------------------*/
listNode ListNode_sortedIntersect(listNode a, listNode b)
{
if(a = NULL)
return b;
if(b == NULL)
return a;
listNode currentA = a;
listNode currentB = b;
listNode pList = NULL;
while( currentA != NULL || currentB != NULL)
{
if( currentB == NULL || (currentA != NULL && currentB != NULL && currentA->data <= currentB->data))
{
ListNode_insertEnd(&pList, currentA->data);
currentA = currentA->next;
}
if( currentA == NULL || (currentA != NULL && currentB != NULL && currentA->data > currentA->data))
{
ListNode_insertEnd(&pList, currentB->data);
currentB = currentB->next;
}
}
return pList;
}
/*--------------------------------------------------------------------------------
function : ListNode_reverse
Purpose : reverse an listNode
Parameters : listNode* sourceRef
Return : NONE
--------------------------------------------------------------------------------*/
int ListNode_reverse(listNode* sourceRef)
{
listNode reverseList = NULL;
listNode temp = NULL;
listNode pList = *sourceRef;
while(pList != NULL)
{
temp = pList;
pList = pList->next;
temp->next = reverseList;
reverseList = temp;
}
*sourceRef = reverseList;
return 0;
}
Raw
linkedlist.h
/********************************************************************************
Product : Linkedlist Library
Module :
Author : Trung Kien - [email protected]
Description : Library for Linkedlist data struct.
********************************************************************************/
#ifndef __LINKED_LIST__
#define __LINKED_LIST__
/*-----------------------------------------------------------------------------*/
/* Header inclusions */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Local Constant definitions */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Local Macro definitions */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Local Data type definitions */
/*-----------------------------------------------------------------------------*/
typedef int item; // Maybe change to meet requirement.
typedef struct node
{
item data;
struct node* next;
}node, *listNode;
/*-----------------------------------------------------------------------------*/
/* Global variables */
/*-----------------------------------------------------------------------------*/
/*-----------------------------------------------------------------------------*/
/* Function prototypes */
/*-----------------------------------------------------------------------------*/
listNode Node_create(item data);
int Node_delete(listNode* pList);
int ListNode_push(listNode* pList, item data);
int ListNode_insertBegin(listNode *pList, item data);
int ListNode_insertEnd(listNode *pList, item data);
int ListNode_insertMid(listNode *pList, item data, int position);
int ListNode_removeBegin(listNode* pList);
int ListNode_removeLast(listNode* pList);
int ListNode_removeMid(listNode* pList, int position);
int ListNode_show(listNode pList);
int ListNode_length(listNode pList);
int ListNode_count(listNode pList, item pattern);
int ListNode_getNth(listNode plist, int position, int *value);
int ListNode_delete(listNode *pList);
int ListNode_sorftedInsert(listNode *pList, item data);
int ListNode_insertSoft(listNode *pList);
int ListNode_append(listNode *a, listNode *b);
int ListNode_frontBackSplit(listNode source, listNode* frontRef, listNode* backRef);
int ListNode_moveNode(listNode *destRef, listNode *sourceRef);
int ListNode_alternatingSplit(listNode source, listNode* EventRef, listNode* OddRef);
listNode ListNode_shuffleMerge(listNode a, listNode b);
int ListNode_mergeSoft(listNode* sourceRef);
listNode ListNode_sortedIntersect(listNode a, listNode b);
int ListNode_reverse(listNode* sourceRef);
// int ListNode_update(listNode *pList, int position);
// int ListNode_search(listNode *pList, item data);
#endif // __LINKED_LIST__
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment