Tuesday, August 01, 2006

Create a linked list with number 0-9 inside:
element* createList() {  element* front = NULL;// first element  element* back = NULL; // last element  int x;  for (x = 0; x < 10; x++) {      element* newnode = new element();      newnode->data = x;      newnode->next = NULL; // this is the end      if (front == NULL) {          front = newnode; //if this is the first node          back = newnode; // it's both the front and back.      }      else{          back->next = newnode; //prev end points to newnode      }      back = newnode; // new end of list  }  return front;}element * elem = createList(); // call in main()

Locate the link list: find the node when data = n

element *Findn(element *elem, int n){  while (elem) {      if (elem->data == n) {          return elem;      }      elem = elem->next;  }  return NULL;}element *locate = Findn(elem, 6);// in main()

int inserthead(element **head, element *newelem){  if (!newelem) return 0;  newelem->next = *head;  *head = newelem;  return 1;}element *newelem;newelem = (element *)malloc(sizeof(element));newelem->data = 12;inserthead(&elem, newelem);

Delete one element:(Deletion and insertion require a pointer to the element immediately preceding the deletion or insertion location)

int delElement(element **elem, element *delelem){  element *temp = *elem;  if (delelem == *elem)// head  {      *elem = delelem->next;      free(delelem);      return 1;  }  while(temp)  {      if (temp->next == delelem)      {          temp->next = delelem->next;          free(delelem);          return 1;      }      temp = temp->next;  }  return 0;}element * delelem = Findn(elem, 12); // in main()delElement(&elem, delelem);

Insert an element before specified elements:

int insertElement(element **elem, element *location, element *insertelem){  element *temp = *elem;  if (location == *elem)// head  {      *elem = insertelem->next;      return 1;  }  while(temp)  {      if (temp->next == location)      {          insertelem->next = location;          temp->next = insertelem;          return 1;      }      temp = temp->next;  }  return 0;}element * location = Findn(elem, 9); // in main()element * insertelem;insertelem = (element*)malloc(sizeof(element));insertelem->data = 33;insertElement(&elem, location, insertelem);

Release the whole linked list: (need two pointers)

void deleteList( element *head){  element *next, *deleteMe;  deleteMe = head;  while(deleteMe)  {      next = deleteMe->next;      free(deleteMe);      deleteMe = next;  }}

Delete the head of a list:

void deleteHead(element **elem){  element *temp;  if(elem && (*elem)) // check for Null list  {      temp = (*elem)->next;      free(*elem);      *elem = temp;  }}

Check the linked list is a circle or not:

Start two pointers at the head of the list Loop infinitely
If the fast pointer reaches a NULL pointer
-Return that the list is NULL terminated
If the fast pointer moves onto or over the slow pointer
-Return that there is a cycle
Advance the slow pointer one node
Advance the fast pointer two nodes

int single_circle(element *elem){element *fast = elem;element *slow = elem;while(1){  if(!fast || !fast->data)      return 0;  else if ( fast == slow || fast->next == slow)      return 1;  else {      fast = fast->next->next;      slow = slow->next;}  }}

element *Reverse (element *elem){  element *result = NULL;  while (elem)  {      element *tmp = elem->next;      elem->next = result;      result = elem;      elem = tmp;  }  return result;}

Reverse, just reverse itself

static void Reverse3(element** elem){  element* result = NULL;  element* current = *elem;  element* tmp;  while (current) {      tmp = current->next; // tricky: note the next node      current->next = result; // move the node onto the result      result = current;      current = tmp;  }  *elem = result;}

Reverse, use recursion:

element *Reverse2(element *elem){  element *temp;  if(elem->next)  {      temp=Reverse2(elem->next);      elem->next->next=elem;      elem->next=NULL;  }  else      temp=elem;  return temp;}

void printList(element * start){  for (; start!=NULL; start=start->next)  {      cout << start->data << " ";  }  cout << endl;}