C 链表的基本操作

根据记忆实现了C的链表基本操作
代码在：http://git.loftor.com/study/c.git/tree/List/List.cpp

// List.c: 主项目文件。
#include <stdio.h>
#include <stdlib.h>

/*双向节点定义*/
typedef struct Node
{
  int value;
  Node * next;
  Node * prev;
} Node;

/*初始化链表*/
Node * createList(int first){
  Node * node = (Node *)malloc(sizeof(Node));
  node->value = first;
  node->next = NULL;
  node->prev = NULL;
  return node;
}

bool isEmptyList(Node **pNode){
  return (*pNode) == NULL;
}


/*指针重置到List头部*/
void resetHead(Node **pNode){
  if (isEmptyList(pNode)){
    (*pNode) = NULL;
  }
  else{
    while ((*pNode)->prev != NULL)
    {
      (*pNode) = (*pNode)->prev;
    }
  }
}

/*指针重置到List头部*/
void resetTail(Node **pNode){
  if (isEmptyList(pNode)){
    (*pNode) = NULL;
  }
  else{
    while ((*pNode)->next != NULL)
    {
      (*pNode) = (*pNode)->next;
    }
  }
}


/*返回List长度*/
int lengthList(Node **pNode){
  resetHead(pNode);
  int length = 0;
  if (isEmptyList(pNode)){
    return length;
  }
  while ((*pNode)->next != NULL)
  {
    length++;
    (*pNode) = (*pNode)->next;
  }
  resetHead(pNode);
  return length;
}

/*打印链表*/
void printfList(Node *pNode){
  if (!isEmptyList(&pNode))
  {
    printf("%d\t", pNode->value);
    while (pNode->next != NULL){
      pNode = pNode->next;
      printf("%d\t", pNode->value);
    }
  }
  printf("\n");
}

/*左边压入一个*/
void leftPush(Node **pNode, int value){
  Node * newNode = (Node *)malloc(sizeof(Node));
  resetHead(pNode);
  newNode->prev = NULL;
  newNode->next = *pNode;
  newNode->value = value;
  if (!isEmptyList(pNode))
  {
    (*pNode)->prev = newNode;
  }
  *pNode = newNode;
}

/*右边压入一个*/
void rightPush(Node **pNode, int value){
  Node * newNode = (Node *)malloc(sizeof(Node));
  resetTail(pNode);
  newNode->next = NULL;
  newNode->prev = *pNode;
  newNode->value = value;

  if (!isEmptyList(pNode))
  {
    (*pNode)->next = newNode;
  }
  else{
    *pNode = newNode;
  }
  resetHead(pNode);
}



/*从左边出一个*/
int leftPop(Node **pNode){
  resetHead(pNode);
  Node *tempNode = *pNode;
  int value = tempNode->value;
  (*pNode) = tempNode->next;
  (*pNode)->prev = NULL;
  free(tempNode);
  return value;
}

/*从右边出一个*/
int rightPop(Node **pNode){
  resetTail(pNode);
  Node *tempNode = *pNode;
  int value = tempNode->value;
  (*pNode) = tempNode->prev;
  (*pNode)->next = NULL;
  resetHead(pNode);
  free(tempNode);
  return value;
}

/*删除指定节点*/
bool removeNode(Node **pNode, int index){
  int length = lengthList(pNode);
  if (length<index) //节点不存在
  {
    return false;
  }
  Node * tempNode = *pNode;
  for (int i = 0; i < index; i++)
  {
    tempNode = tempNode->next;
  }
  if (tempNode->prev != NULL)
  {
    tempNode->prev->next = tempNode->next;
  }
  if (tempNode->next != NULL)
  {
    tempNode->next->prev = tempNode->prev;
  }
  free(tempNode);
  return true;
}

/*销毁List*/
bool destroyList(Node **pNode){
  resetHead(pNode);
  if (pNode==NULL)
  {
    return true;
  }
  Node *head = (*pNode);
  if (head->next == NULL)
  {
    free(head);
    return true;
  }

  while ((*pNode)->next != NULL)
  {
    (*pNode) = (*pNode)->next;
    free((*pNode)->prev);
  }
  *pNode = NULL;
  return true;
}



int main()
{
  //Node * list = createList(1);
  Node * list = NULL;

  rightPush(&list, 2);
  rightPush(&list, 3);
  rightPush(&list, 4);
  rightPush(&list, 5);
  rightPush(&list, 6);
  rightPush(&list, 7);
  leftPush(&list, 1);
  removeNode(&list, 4);
  printf("链表长度为:%d\n", lengthList(&list));

  int value = leftPop(&list);
  value = rightPop(&list);

  printf("链表长度为:%d\n", lengthList(&list));
  printfList(list);
  destroyList(&list);
  return 0;
}