FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

C语言通用数据结构_LinkedList

FunctionGHW posted @ 2013年4月30日 15:13 in 数据结构 with tags C Linked List 数据结构 优化 , 2623 阅读

此链表为双向链表(Doubly-Linked List),LinkedList的声明稍微奇葩了些, 主要是为那些频繁的反复的插入节点和删除节点的应用而优化。对于其他的情况,性能应该会低一些。

设计思路是:如果删除了一个节点, 并不会立即free掉此节点,而是扔到节点池(nodes pool)里,等到创建新的节点时, 直接拿出来用而不用开辟新的空间,从而避免频繁的malloc操作,节点池其实就是个单向链表 (尽管里面的节点都有next和prev指针,我们只使用next)。一个明显的副作用就是空间开销可能会大些, 因此节点池的大小需要设置的合理些。

#include <stddef.h>

 /*
#ifndef BYTE
#define BYTE unsigned char
#endif
 */
typedef unsigned char BYTE;

struct LinkedList;
struct LnkLstNode;

typedef struct LinkedList LinkedList;
typedef struct LnkLstNode LnkLstNode;

struct LnkLstNode
{
    BYTE* data;

    LinkedList* owner;//which linked list the node was contained;
    LnkLstNode* next;
    LnkLstNode* prev;
};

struct LinkedList
{
    size_t count;
    size_t elemt_size;
    LnkLstNode* header;
    LnkLstNode* rear;

    /* a nodes pool is used for
     * storeing nodes temporarily,
     * which were removed;*/
    size_t pool_size;
    // maximum number of nodes that the pool could contain;
    size_t pool_count;
    //the number of nodes actually contained in nodes pool;
    LnkLstNode* nodes_pool;
};

//==========================================

//Create a new linked list;
LinkedList* new_lnklst(const size_t elemt_size, const size_t pool_size);

//Is the list empty?;
int lnklst_is_empty(const LinkedList* lst);
//Is the nodes pool empty?;
int lnklst_is_pool_empty(const LinkedList* lst);
//Is the nodes pool full?;
int lnklst_is_pool_full(const LinkedList* lst);
//Get the number of nodes actually contained in the list;
size_t lnklst_count(const LinkedList* lst);
//Get the size of element that contained in the list;
size_t lnklst_elemt_size(const LinkedList* lst);
//Get maximum number of nodes that the pool could contain;
size_t lnklst_pool_size(const LinkedList* lst);
//Get the number of nodes actually contained in nodes pool;
size_t lnklst_pool_count(const LinkedList* lst);

//Get the first element contained in the list;
BYTE* lnklst_first_elemt(const LinkedList* lst);
//Get the last element contained in the list;
BYTE* lnklst_last_elemt(const LinkedList* lst);

//Get the first node contained in the list;
LnkLstNode* lnklst_first_node(const LinkedList* lst);
//Get the last node contained in the list;
LnkLstNode* lnklst_last_node(const LinkedList* lst);

//Get the node contained in the list which has the specified position;
LnkLstNode* lnklst_node_at(const LinkedList* lst, size_t index);

//Add an element to the header of the list;
void lnklst_add_first(LinkedList* lst, const BYTE* elemt);
//Add an element to the rear of the list;
void lnklst_add_last(LinkedList* lst, const BYTE* elemt);
//Add an element before the specified node;
void lnklst_add_before(LnkLstNode* node, const BYTE* elemt);
//Add an element after the specific node;
void lnklst_add_after(LnkLstNode* node, const BYTE* elemt);

//Remove node from the header of the list;
void lnklst_remove_first(LinkedList* lst);
//Remove node from the rear of the list;
void lnklst_remove_last(LinkedList* lst);
//Remove a node contained in the list using its pointer;
void lnklst_remove(LnkLstNode* node);

//Find the first node that contains the specified value;
LnkLstNode* lnklst_find(const LinkedList* lst, const BYTE* elemt, int (*cmp)(const BYTE*, const BYTE*));
//Find the last node that contains the specified value;
LnkLstNode* lnklst_find_last(const LinkedList* lst, const BYTE* elemt, int (*cmp)(const BYTE*, const BYTE*));

//Travel the list, perform the specified action on each node;
//Like in java or C#, we assume that 'foreach' should not change the elemt;
void lnklst_foreach(LinkedList* lst, void (*action)(const BYTE* elemt));
//Remove all nodes in the list;
void lnklst_empty(LinkedList* lst);
//Empty the nodes pool of the list;
void lnklst_empty_pool(LinkedList* lst);
//Dispose the linked list;
void lnklst_dispose(LinkedList* lst);
                
                

我自己写的一个实现:CLinkedList。 在头和尾都加了一个哨兵节点,因为这样一些操作写起来容易些。如果真的有频繁的增删操作, 性能上确实有明显的提升。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter