[数据结构] 单链表

一、C语言实现

1.1 结构体定义

typedef int ElementType;

// 定义一个链表结构体
struct ListNode {
    ElementType val;
    struct ListNode *next;
};

1.2 相关方法实现

#include <stdio.h>
#include <malloc.h>

typedef int ElementType;

// 定义一个链表结构体
struct ListNode {
    ElementType val;
    struct ListNode *next;
};

/**
 * 创建一个链表
 * @param head
 * @param length
 */
void create_list(struct ListNode **head, int length) {
    *head = (struct ListNode *) malloc(sizeof(struct ListNode));
    (*head)->next = NULL;
    struct ListNode *p;
    for (int i = 0; i < length; ++i) {
        p = (struct ListNode *) malloc(sizeof(struct ListNode));
        p->val = i + 1;
        p->next = (*head)->next; // 头插法构建链表
        (*head)->next = p;
    }
}

/**
 *
 * @param head 线性表head，头节点为第零个节点
 * @param index 获取index位置的元素
 * @param element 出参
 * @return
 */
int get_element(struct ListNode *head, int index, ElementType *element) {
    int cur = 0;
    struct ListNode *cur_ptr = head->next;
    while (cur_ptr && cur != index) {
        cur_ptr = cur_ptr->next;
        ++cur;
    }
    if (!cur_ptr || cur > index) {
        return -1;
    }
    *element = cur_ptr->val;
    return 0;
}

int get_size(struct ListNode *head) {
    if (!head) { return -1; }
    int size = 0;
    struct ListNode *cur = head;
    while (cur != NULL) {
        cur = cur->next;
        size++;
    }
    return size;
}

/**
 *
 * @param head 线性表head，头节点为第零个节点
 * @param index 在index之前的一个位置插入元素
 * @param e 待插入的元素
 * @return e
 */
int insert_element(struct ListNode *head, int index, ElementType e) {
    if (!head) {
        return -1;
    }
    // 找到index-1的节点
    int cur = 1;
    struct ListNode *cur_ptr = head;
    while (cur_ptr && cur < index) {
        cur_ptr = cur_ptr->next;
        ++cur;
    }
    // 第index个节点不存在
    if (!cur_ptr || cur > index) {
        return -1;
    }
    struct ListNode *node = (struct ListNode *) malloc(sizeof(struct ListNode));
    node->val = e;
    node->next = cur_ptr->next;
    cur_ptr->next = node;
    return 0;
}

/**
 *
 * @param head 线性表head，头节点为第零个节点
 * @param index 删除index位置的元素
 * @param e 待删除的元素
 * @return e
 */
int delete_element(struct ListNode *head, int index, ElementType *e) {
    if (!head) {
        return -1;
    }
    // 找到index-1的节点
    int cur = 1;
    struct ListNode *cur_ptr = head;
    while (cur_ptr && cur < index) {
        cur_ptr = cur_ptr->next;
        ++cur;
    }
    // 第index个节点不存在
    if (!cur_ptr || cur > index) {
        return -1;
    }
    struct ListNode *q;
    q = cur_ptr->next;
    cur_ptr->next = q->next;
    *e = q->val;
    free(q);
    return 0;
}


int main() {
    struct ListNode *node;
    create_list(&node, 10); // [0 10 9 8 7 6 5 4 3 2 1]
    int num;
    get_element(node, 2, &num);
    insert_element(node, 2, 100);
    delete_element(node, 1, &num);
    int size = get_size(node);
    for (int i = 0; i < size; ++i) {
        printf("%d ", node->val);
        node = node->next;
    }
    free(node);
}

二、Java语言实现