Linked list examples

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()

Add element in head part:

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;}
  }
}

Reverse linked list:

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;
}

Print out the linked list:

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

Check the following link for more information: http://cslibrary.stanford.edu/105/