Go to Github to download the source codes.

1. IDE

Mac OS EI Capitan 10.11.3,Xcode 7.2 (7C68),Mou 0.8.7

2. Abstrat

The basic operations of single linked list in C langeage below:
本文主要讲单链表以下这些基本操作：

• Create 创建
• Query 查询
• Add 添加
• Modify 修改
• Sort 排序
• Delete 删除
• Ergodic 遍历
• Other 其它

Previously,it is best for you to learn the typedef struct syntax first if you have not learned
or forget its usage.
如果你没有学过结构体定义的语法或记不清，请先学习它的用法。
结构体定义：struct与typedef struct 用法详解和用法小结
结构体定义 typedef struct 用法详解和用法小结

3. Basic operations

3.1 Create

• Create a link with data [0…7] automatically.
  自动创建结点数据从0到7的单链表。

LinkedList_Long createLinked() {
    LinkedList_Long head = createHeadNode();
    if (head == NULL) {
        return NULL;
    }
    LongNodeData amount = 0;
    LinkedList_Long pLast = NULL;
    for (LongNodeData index = 0; index < 8; index++) {
        LinkedList_Long pNext = createHeadNode();
        if (pNext == NULL) {
            return head;
        }
        if (!index) {//append the first node to header
            pLast = pNext;
            head->next = pLast;

        }else {//appending the node to last node
            pLast->next = pNext;
            pLast = pNext;
        }
        pNext->data = index;
        amount++;
    }
    head->data = amount;

    return head;
}

• Create link and receive user’s input continously unless entering the exitData to stop.
  创建链表并连续接收用户输入的数据，输入指定的数据来结束此次创建。

LinkedList_Long createLinkedListWithExitData(LongNodeData exitData,bool isAtHeader) {
    LinkedList_Long head = createHeadNode();
    if (head == NULL) {
        return NULL;
    }
    LongNodeData amount = 0;
    LinkedList_Long pLast = isAtHeader ? NULL : head;

    while (1) {
        LinkedList_Long pNext = createHeadNode();
        if (pNext == NULL) {
            break;
        }
        printf("Enter an integer data,enter %lld to exit the creating.\n",exitData);
        scanf("%lld",&pNext->data);
        if (pNext->data == exitData) {
            break;
        }
        if (isAtHeader) {//add to header
            if (amount != 0) {//is not the first node
                pNext->next = pLast;
            }
        }else {//add to tail
            pLast->next = pNext;
        }
        pLast = pNext;
        amount++;
    }
    head->data = amount;
    if (isAtHeader) {
        head->next = pLast;
    }
    return head;
}

3.2 Query

• Query the node at index of the link.
  根据索引获取结点。

LinkedList_Long nodeAtIndex(LinkedList_Long head,LongNodeData index) {
    if (head == NULL) {
        return NULL;
    }
    if (index < 0) {
        printf("Please enter an non-negative integer.\n");
        return NULL;
    }
    if (index >= head->data) {
        printf("The index %lld beyond bounds [0...%lld],and \n"
               "please be sure the index is counted from 0.\n",index,head->data - 1);
        return NULL;
    }

    LinkedList_Long pNext = head->next;
    LongNodeData num = 0;
    while (pNext && num < index) {
        pNext = pNext->next;
        num++;
    }
    return pNext;
}

• Query the lastest node of the link.
  获取链表最后一个结点。

LinkedList_Long lastNodeOfLinkedList(LinkedList_Long head) {
    if (head == NULL) {
        return NULL;
    }
    LinkedList_Long pNext = head->next;
    if (pNext == NULL) {
        return NULL;
    }
    while (pNext->next) {
        pNext = pNext->next;
    }
    return pNext;
}

3.3 Insert

• Insert a new node,inputed by user instantly, at index of the link.
  在指定索引插入节点

LinkedList_Long insertOneNodeAtIndex(LinkedList_Long head) {
    if (head == NULL) {
        printf("Insert failed,as the linked list is NULL.");
        return head;
    }
    LinkedList_Long node = createHeadNode();
    if (node == NULL) {
        printf("Insert failed for the sake of memory error.\n");
        return head;
    }
    LongNodeData index = 0;
    printf("Enter the index,a non-negative integer,as the insert location.\n");
    scanf("%lld",&index);
    while (!isIndexInsideLinkedList(index, head)) {
        printf("please enter agan.\n");
        index = 0;
        scanf("%lld",&index);
    }
    printf("please enter the data.\n");
    scanf("%lld",&node->data);

    if (index < 0) {
        index = 0;
    }
    return insertNodeIntoListAtIndex(head, node, index);
}

• Insert the node into the link at index of the link.
  插入一个结点到链表的指定索引

LinkedList_Long insertNodeIntoListAtIndex(LinkedList_Long head,LinkedList_Long node,LongNodeData index) {
    if (head == NULL) {
        return NULL;
    }
    if (node == NULL) {
        printf("Insert failed,because the node is NULL.\n");
        return head;
    }
    if ((*head).next == NULL) {//node count is 0
        (*head).next = node;
        return head;
    }
    if (index > (*head).data - 1) {
        LinkedList_Long tailNode = lastNodeOfLinkedList(head);
        (*tailNode).next = node;

    }else {
        if (index == 0) {
            (*node).next = (*head).next;
            (*head).next = node;
        }else {
            LinkedList_Long lastNode = nodeAtIndex(head, index - 1);
            if (lastNode == NULL) {
                printf("Got node at index failed!\n");
                return head;
            }
            (*node).next = (*lastNode).next;
            (*lastNode).next = node;
        }
    }

    return head;
}

3.4 Modify

• Exchage two data of two nodes.
  交换两个结点的数据。

void exchangeTwoNodeData(LinkedList_Long nodeLeft,LinkedList_Long nodeRight) {
    LongNodeData data = nodeLeft->data;
    nodeLeft->data = nodeRight->data;
    nodeRight->data = data;
}

• Exchage two nodes’ data of the link in the two indexs.
  通过索引交换两个结点。

LinkedList_Long exchageTwoNode (LinkedList_Long head,LongNodeData indexLeft,LongNodeData indexRight) {
    if (head == NULL) {
        printf("Exchaged failed.The linkedList is NULL\n");
        return head;
    }
    if (head->data < 1) {
        printf("Exchaged failed.The linkedList has nodes less than 2.\n");
        return head;
    }
    if (indexRight == indexLeft) {
        return head;
    }
    if (!isIndexInsideLinkedList(indexLeft, head) || !isIndexInsideLinkedList(indexRight, head)) {
        return head;
    }

    printf("Begin exchaging two node.\n");
    LinkedList_Long nodeLeft = nodeAtIndex(head, indexLeft);
    LinkedList_Long nodeRight = nodeAtIndex(head, indexRight);
    exchangeTwoNodeData(nodeLeft, nodeRight);
    return head;
}

• Revert the link by operating its datas.
  链表逆置。

void revertLinkedList (LinkedList_Long head) {
    if (head == NULL) {
        printf("Revert failed,the linkedList is NULL.\n");
        return;
    }
    LongNodeData count = head->data - 1;
    if (count < 2) {
        return;
    }
    for (LongNodeData index = 0; index < count; index++,count--) {
        exchageTwoNode(head, index, count);
    }
}

3.5 Sort

Sort the link with two ways,by operating the node count or node pointer.
通过操作链表结点个数或者结点指针对链表进行排序。

LinkedList_Long sortLinkedList(LinkedList_Long head,bool accending) {
    //mode 1,using node count
    if (head->data < 1) {
        return head;
    }
    LinkedList_Long node = head->next;
    for (LongNodeData row = 0; row < head->data - 1; row++) {
        LinkedList_Long pNext = node->next;
        if (pNext == NULL || node == NULL) {
            break;
        }
        for (LongNodeData coloum = 0; coloum < head->data; coloum++) {
            if (accending) {
                if (node->data > pNext->data) {
                    exchangeTwoNodeData(node, pNext);
                }
            }else {
                if (node->data < pNext->data) {
                    exchangeTwoNodeData(node, pNext);
                }
            }
            pNext = pNext->next;
            if (pNext == NULL) {
                break;
            }
        }
        node = node->next;
    }

    return head;

    //mode 2,using pointer
    if (head->next == NULL) {
        return head;
    }
    LinkedList_Long qNode = head->next;
    while (qNode) {
        LinkedList_Long qNext = qNode->next;
        while (qNext) {
            if (accending) {
                if (qNode->data > qNext->data) {
                    exchangeTwoNodeData(qNode, qNext);
                }
            }else {
                if (qNode->data < qNext->data) {
                    exchangeTwoNodeData(qNode, qNext);
                }
            }
            qNext = qNext->next;
        }
        qNode = qNode->next;
    }
    return head;
}

3.6 Delete

• Delete one node at the index of the link.
  删除一个指定索引的结点。

LinkedList_Long deleteNodeAtIndex (LinkedList_Long head,LongNodeData index) {
    if (head == NULL) {
        printf("Delete failed,the linked list is NULL.\n");
        return head;
    }
    if (head->next == NULL) {
        printf("Delete failed,the linked list's node count is 0.\n");
        return head;
    }
    if (index >= head->data) {
        printf("Delete failed,index %lld beyond bounds [0...%lld].\n",index,head->data);
        return head;
    }
    if (index == 0) {
        LinkedList_Long node = nodeAtIndex(head, 0);
        head->next = node->next;
        node->next = NULL;
        free(node);

    }else {
        LinkedList_Long node = nodeAtIndex(head, index - 1);
        LinkedList_Long nodeDelete = node->next;
        node->next = nodeDelete->next;
        nodeDelete = NULL;
        free(nodeDelete);

    }
    head->data--;
    return head;
}

• Delete the whole link and release the memory,release the header node if neccessary.
  整个链表删除及释放内存，有需要可把头结点也删除。

LinkedList_Long deleteLinkedList (LinkedList_Long head) {
    if (head == NULL) {
        printf("The linkedList is NULL.\n");
        return NULL;
    }
    LinkedList_Long list = head->next;
    if (list == NULL) {
        printf("The LinkedList has no node.\n");
        return head;
    }
    LongNodeData index = 0;
    while (list) {
        LinkedList_Long node = list;
        list = list->next;
        printf("delete node %lld at index %lld.\n",node->data,index++);
        node->next = NULL;
        node = NULL;
        free(node);
        head->data--;
    }
    head->next = NULL;
    free(head->next);

    return head;
}

3.7 Ergodic

• Print the node’s data.
  打印指定结点的数据。

void printLinkedNode(LinkedList_Long headNode) {
    if (headNode == NULL) {
        printf("The node is NULL.\n");
        return;
    }
    printf("The node data is %lld.\n",headNode->data);
}

• Print the whole link’s datas.
  打印链表的所有数据。

void printLinkedList(LinkedList_Long headNode) {
    LinkedList_Long pNext = headNode->next;
    printf("The linked list has %lld nodes,it is : \n",headNode->data);

    while (pNext != NULL) {
        printf("%lld, ",pNext->data);
        pNext = pNext->next;
    }
    printf("\n");
}

3.8 Other

• Judging the index is beyond the link or not.
  判断索引是否超出链表范围。

bool isIndexInsideLinkedList(LongNodeData index,LinkedList_Long head) {
    if (index >= head->data) {
        printf("Index %lld beyond bounds [0...%lld].\n",index,head->data - 1);
        return 0;
    }
    return 1;
}

4. Test guide

Testing the create function following is primary.The other create functions is similar.
首先测试下面创建链表的方法，其它创建链表的方法也类似。

    LinkedList_Long head = createLinked();
    printLinkedList(head);

Other testing is the same as the following sort test function.
其它函数的测试也和下面排序的函数一样。

    LinkedList_Long head = createLinked();
    printLinkedList(head);
    head = sortLinkedList(head, 1);
    printf("*******  Sort results  *****\n");
    printLinkedList(head);

Copyright reserved,reprinted from dabin’s Data structure - Single linked list’s basic operations - C langeage.
转载请标明出处，转自大彬的 数据结构-单链表基本操作-C语言。