C语言通用数据结构_LinkedList

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

此链表为双向链表(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。在头和尾都加了一个哨兵节点，因为这样一些操作写起来容易些。如果真的有频繁的增删操作，性能上确实有明显的提升。

[回复]

Liwovosa 说:
2021年4月21日 16:24

Thank you for some other informative website. The place else may just I get that kind of information written in such a perfect method? I have a venture that I am simply now running on, and I’ve been at the glance out for such info. https://ww-123movies.com/

[回复]

Liwovosa 说:
2021年4月24日 16:56 I know this is one of the most meaningful information for me. And I'm animated reading your article. But should remark on some general things, the website style is perfect; the articles are great. Thanks for the ton of tangible and attainable help. fx마진거래

[回复]

jackjohnny 说:
2021年5月01日 04:14

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. disney plus for free with amazon prime

[回复]

Liwovosa 说:
2021年5月02日 17:08

This is a good post. This post gives truly quality information. I’m definitely going to look into it. Really very useful tips are provided here. Thank you so much. Keep up the good works. fx사이트

[回复]

Liwovosa 说:
2021年5月03日 19:35

This article was written by a real thinking writer. I agree many of the with the solid points made by the writer. I’ll be back. 파워볼클리닉

[回复]

jackjohnny 说:
2021年5月04日 19:00

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. indian visa online

[回复]

Liwovosa 说:
2021年5月04日 20:10

You there, this is really good post here. Thanks for taking the time to post such valuable information. Quality content is what always gets the visitors coming. How to become a merchant service provider

[回复]

Liwovosa 说:
2021年5月05日 17:05

I gotta favorite this website it seems very helpful . how to start a payment processing company

[回复]

Liwovosa 说:
2021年5月05日 19:35

I know this is one of the most meaningful information for me. And I'm animated reading your article. But should remark on some general things, the website style is perfect; the articles are great. Thanks for the ton of tangible and attainable help. elling credit card terminals

[回复]

Liwovosa 说:
2021年5月06日 18:22

You delivered such an impressive piece to read, giving every subject enlightenment for us to gain information. Thanks for sharing such information with us due to which my several concepts have been cleared. 홀덤사이트

[回复]

kalenmok 说:
2021年5月09日 19:08

Thank you for your post. Really looking forward to read more. Cool.<a href="https://forums.prosportsdaily.com/member.php?970725-RolfUeberroth&tab=aboutme&simple=1">gewinnspielautomaten.com</a>

[回复]

kalenmok 说:
2021年5月09日 19:09

Thank you for your post. Really looking forward to read more. Cool.[url=https://forums.prosportsdaily.com/member.php?970725-RolfUeberroth&tab=aboutme&simple=1]gewinnspielautomaten.com[/url]

[回复]

gewinnspielautomaten 说:
2021年5月09日 19:09

Really appreciate you sharing this blog post. Really thank you! Really Cool.

[回复]

gewinnspielautomaten 说:
2021年5月09日 19:10

Really appreciate you sharing this blog post. Really thank you! Really Cool.

[回复]

jackjohnny 说:
2021年5月11日 18:19

Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. how to get free uc in pubg mobile

[回复]

Liwovosa 说:
2021年5月17日 19:16

Wow, cool post. I'd like to write like this too - taking time and real hard work to make a great article... but I put things off too much and never seem to get started. Thanks though. บาคาร่า99

[回复]

Liwovosa 说:
2021年5月18日 22:59 I was reading your article and wondered if you had considered creating an ebook on this subject. Your writing would sell it fast. You have a lot of writing talent. canadian online casino

[回复]

Liwovosa 说:
2021年5月19日 17:23

When you use a genuine service, you will be able to provide instructions, share materials and choose the formatting style. best online casino canada

[回复]

jackjohnny 说:
2021年5月19日 20:01

[回复]

لی ویوسوہ ہو یار 说:
2021年5月20日 19:29 This blog website is pretty cool! How was it made ! polskie kasyno online

[回复]

لی ویوسوہ ہو یار 说:
2021年5月20日 22:15

Whenever I have some free time, I visit blogs to get some useful info. Today, I found your blog with the help of Google. Believe me; I found it one of the most informative blog. online casino

[回复]

لی ویوسوہ ہو یار 说:
2021年5月23日 16:13

You completed a few fine points there. I did a search on the subject and found nearly all persons will go along with with your blog. casinos online

[回复]

لی ویوسوہ ہو یار 说:
2021年5月23日 20:56

Someone Sometimes with visits your blog regularly and recommended it in my experience to read as well. The way of writing is excellent and also the content is top-notch. Thanks for that insight you provide the readers! raspadinhas online

[回复]

لی ویوسوہ ہو یار 说:
2021年5月26日 20:12

This blog website is pretty cool! How was it made ! Vacation rental cleaning checklist

[回复]

jackjohnny 说:
2021年5月26日 20:57

[回复]

<a href="https://www 说:
2021年6月01日 23:58

Cool stuff you have got and you keep update all of us.

[回复]

biaakhan 说:
2021年6月02日 23:54

Thanks, that was a really cool read! Job

[回复]

jackjohnny 说:
2021年6月10日 20:24

This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. Citronella oil Manufacturers in India

[回复]

jackjohnny 说:
2021年6月17日 16:07

i never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. free coin master spins

[回复]

jackjohnny 说:
2021年6月17日 22:06

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with extra information? It is extremely helpful for me. 먹튀사이트

[回复]

jackjohnny 说:
2021年6月20日 16:05

A very awesome blog post. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. Free Diamonds Generator

[回复]

jackjohnny 说:
2021年6月23日 18:13

When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your. https://www.towelsforthebeach.com/

[回复]

Kamla 说:
2021年6月23日 18:54

I value the blog article. Really looking forward to read more. Really Great.
<a href="https://forum.ct8.pl/member.php?action=profile&uid=63891">gewinn spielautomaten</a>

[回复]

Kamla 说:
2021年6月23日 18:55

Wow great blog article. Really thank you! Awesome. [url=https://forum.ct8.pl/member.php?action=profile&uid=63891]gewinn spielautomaten[/url]

[回复]

jackjohnny 说:
2021年6月24日 17:14

Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject. Towelsforthebeach.com

[回复]

www.spielautomaten-d 说:
2021年6月24日 20:50

Really informative article post. Will read on...

[回复]

jackjohnny 说:
2021年6月26日 22:54

Thank you for the update, very nice site.. 안전놀이터

[回复]

jackjohnny 说:
2021年6月29日 23:48

I have bookmarked your blog, the articles are way better than other similar blogs.. thanks for a great blog! Neuseeland Visum

[回复]

online casino deutsc 说:
2021年7月03日 22:14

I cannot thank you enough for the blog article. Really thank you!

[回复]

arkseo 说:
2021年7月05日 13:02

Please continue this great work and I look forward to more of your awesome blog posts. how to become a payment service provider

[回复]

jackjohnny 说:
2021年7月05日 20:06

This is such a great resource that you are providing and you give it away for free. สล็อต

[回复]

arkseo 说:
2021年7月06日 12:56

Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place.. all seo tools in one

[回复]

jackjohnny 说:
2021年7月12日 14:21

This particular papers fabulous, and My spouse and i enjoy each of the perform that you have placed into this. I’m sure that you will be making a really useful place. I has been additionally pleased. Good perform! 안전놀이터

[回复]

jackjohnny 说:
2021年7月13日 17:05

Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome! Brawl Stars Free Gems Generator

[回复]

jackjohnny 说:
2021年7月14日 17:28

https://www.therestaurantsweb.com/board/board_topic/3906811/5552504.htm?page=1

[回复]

mobilebet 说:
2021年7月16日 02:18

I appreciate you sharing this blog post. Really looking forward to read more. Great.

[回复]

comeon 说:
2021年7月16日 02:19

Major thanks for the article. Will read on...

[回复]

online casino mit au 说:
2021年7月26日 22:26

Thanks for the post. Thanks Again. Really Cool.

[回复]

www meinvz de login 说:
2021年7月31日 21:34

I cannot thank you enough for the article. Thanks Again. Really Cool.

[回复]

aman 说:
2021年8月05日 20:40

I truly enjoy the site. Nice information, thank you for sharing it <a href="https://4anime.click/">4anime</a>

[回复]

Arkseo 说:
2021年8月30日 12:56

Positive site, where did u come up with the information on this posting? I'm pleased I discovered it though, ill be checking back soon to find out what additional posts you include. Search Engines

[回复]

Arkseo 说:
2021年9月04日 14:00

Nice knowledge gaining article. This post is really the best on this valuable topic. merchant processing sales jobs

[回复]

Arkseo 说:
2021年9月04日 21:31

Thank you so much for the post you do. I like your post and all you share with us is up to date and quite informative, i would like to bookmark the page so i can come here again to read you, as you have done a wonderful job. how to become a payment service provider

[回复]

Arkseo 说:
2021年9月06日 12:48

Thank you again for all the knowledge you distribute,Good post. I was very interested in the article, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards, selling credit card processing

[回复]

Arkseo 说:
2021年9月10日 12:33

This was a really great contest and hopefully I can attend the next one. It was alot of fun and I really enjoyed myself.. merchant sales rep, merchant services

[回复]

instagram carousel d 说:
2021年9月30日 20:50

Thank you ever so for your article. Want more.

[回复]

Digital Ali 说:
2021年10月07日 22:37

nice bLog! its interesting. thank you for sharing.... เว็บพนันออนไลน์ ดีที่สุด

[回复]

Digital Ali 说:
2021年10月08日 14:11

Pretty good post. I have just stumbled upon your blog and enjoyed reading your blog posts very much. I am looking for new posts to get more precious info. Big thanks for the useful info. cheap transcription services

[回复]

Digital Ali 说:
2021年10月09日 18:31

Excellent .. Amazing .. I’ll bookmark your blog and take the feeds also…I’m happy to find so many useful info here in the post, we need work out more techniques in this regard, thanks for sharing. คาสิโนออนไลน์ฟรีเงิน

[回复]

Digital Ali 说:
2021年10月11日 11:58

In the world of www, there are countless blogs. But believe me, this blog has all the perfection that makes it unique in all. I will be back again and again. white and gold tuxedo

[回复]

seoservise 说:
2021年10月26日 01:52

This blog is so nice to me. I will keep on coming here again and again. Visit my link as well.. voyance telephone

[回复]

Digital Ali 说:
2021年10月27日 12:28

Thank you so much as you have been willing to share information with us. We will forever admire all you have done here because you have made my work as easy as ABC. best hoverboard for adults

[回复]

Digital Ali 说:
2021年11月04日 12:53

This is a brilliant blog! I'm very happy with the comments!.. situs judi pkv games

[回复]

Liwovosa 说:
2021年12月21日 21:47

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. 안전놀이터

[回复]

johnyking 说:
2021年12月22日 04:38

I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. 토토사이트

[回复]

Liwovosa 说:
2021年12月26日 03:31

This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article. Dynavap 2021

[回复]

Liwovosa 说:
2021年12月27日 19:13 I can’t believe focusing long enough to research; much less write this kind of article. You’ve outdone yourself with this material without a doubt. It is one of the greatest contents. outlook 365

[回复]

Liwovosa 说:
2021年12月29日 14:56

Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts. 토토사이트

[回复]

Liwovosa 说:
2021年12月29日 22:19

I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. metal push button switch

[回复]

Liwovosa 说:
2022年1月01日 22:51 Succeed! It could be one of the most useful blogs we have ever come across on the subject. Excellent info! I’m also an expert in this topic so I can understand your effort very well. Thanks for the huge help. Farmhouse near chennai

[回复]

ArtemSr 说:
2022年12月19日 23:01

Thanks for another great post, man! Hope to see more post like this without that much spam. If you need any help with comment section or any other IT Support, feel free to reach out to EB Solution.

[回复]

Emergency visa to In 说:
2023年2月05日 17:34

The India Business E-Visa is an electronic visa that allows individuals to enter India for business purposes. It is available to citizens of more than 160 countries and can be obtained online through the evisastoindia.org website. It is typically valid for a period of six months to five years, depending on the purpose of your visit and the length of time you need to stay in India. The India Business E-Visa is valid for a period of up to one year and allows for multiple entries into India. It is generally easier and quicker to obtain an e-Visa than a traditional visa, as it can be obtained entirely online and does not require a visit to a consulate or embassy.

[回复]

RAHEEL 说:
2023年3月05日 05:35

Great dispatch! The small business is very acquiring more likely to much more than of which truth, is very neighborly this friend. Also fantastic blog site in this posting affecting the vast majority of high-priced truth persons gain. Pre-book from the useful process your are accomplishing in this posting. 슬롯 커뮤니티

[回复]

SEO 说:
2023年9月05日 17:34

When you use a genuine service, you will be able to provide instructions, share materials and choose the formatting style. EuroTogel Login

[回复]

ZOHAIB 说:
2023年10月25日 21:23

While i get someone to this specific web site along with recognize obtaining valuable home elevators the exact same troubles. battery wall sconce

[回复]

ZOHAIB 说:
2023年10月29日 16:53

Beaver declares that whenever my partner and i furthermore have got just like enthrallment, you should comprehend the particular site in this post: wcofun

[回复]

ZOHAIB 说:
2023年11月30日 23:28

Mmm.. estimable if you are by means of kinds report or even suggest, in any respect, Once i repute I will furthermore training strong designed for the particular contain website want Once i take part in several salubrious in addition stored updated topsy-turvy along with your place. anoboy

[回复]

zohaib malik 说:
2023年12月23日 17:22

I personally like your post; you have shared good insights and experiences. Keep it up. Cuevana 3

[回复]

zohaib malik 说:
2023年12月26日 02:40

Excellent article. I want to thank you for this informative read; I really appreciate sharing this great post. Keep up your work! www.paybyplate.com

[回复]

zohaib malik 说:
2024年1月06日 22:54 You amazingly have terrific article content. Cheers for sharing your blog site. Thank you for sharing. free movies online

[回复]

zohaib malik 说:
2024年1月08日 21:56

You make so many great points here that I read your article a couple of times. This is great content for your readers. Best Point Online

[回复]

zohaib malik 说:
2024年1月22日 15:25 Hi there! You make so many good points here that I read your article a couple of times. This is really nice content for your readers. watch free movies online

[回复]

zohaib malik 说:
2024年1月25日 16:21

Excellent article. I want to thank you for this informative read; I really appreciate sharing this great post. Keep up your work! capcut templates

[回复]

zohaib malik 说:
2024年1月28日 20:00

I enjoyed reading this post such an interesting info post. Thanks for providing good info. Glucoberry

[回复]

Global News Hub 说:
2024年2月01日 01:42

Reap the benefits of largely advanced chemicals -- you'll discover your ex intended for:

[回复]

zohaib malik 说:
2024年2月12日 23:53

I’m happy to find so many useful info here in the post, thanks for sharing. I’ll bookmark your blog and take the feeds also! juwa download

[回复]

zohaib malik 说:
2024年2月18日 23:01 Together with that website website, you'll see kinds consideration, you could begin to be able to had in which. Bulk Cement Booking

[回复]

Ubaid ul Hassan 5th 说:
2024年2月23日 07:28

I get pleasure from that superb write-up that you've got presented for people like us. When i reassure this will possibly be necessary for the majority of people. Ubaid ul Hassan 5th

[回复]

먹튀검증사이트 说:
2024年3月11日 02:47

And for that reason heap to occur much more than people superb web site. Your web site procures all people an exceptional alternate of gratifying.. Salubrious heap on the earth. 먹튀검증사이트

[回复]

best place to buy Se 说:
2024年3月18日 03:35

As i propose to her to help the woman just high quality jointly with reputable truth, so view the piece:

[回复]

zohaib malik 说:
2024年3月22日 04:57

Excellent article. I want to thank you for this informative read; I really appreciate sharing this great post. Keep up your work! plumbing Langley bc

[回复]

raheel 说:
2024年3月28日 06:21 But you might get launched it's essential, the idea yet again brings an affiliate site some tougher leading online site:

[回复]

zohaib malik 说:
2024年3月28日 06:24

Thanks for this great post, I find it very interesting and very well thought out and put together. I look forward to reading your work in the future. satta matka result

[回复]

zohaib malik 说:
2024年3月29日 04:51

I'm amazed by the variety of styles offered by interior designers in Namakkal. interior design 2bhk

[回复]

arjun 说:
2024年4月15日 21:37

The spacious living areas are adorned with plush sofas and intricately crafted furniture, creating a perfect setting for relaxing or entertaining guests. The bedrooms exude comfort and sophistication, featuring luxurious linens, soft pillows, and breathtaking views of the surrounding landscape. Each room has its own en-suite bathroom with deluxe fixtures and spa-like amenities that guarantee a rejuvenating experience.

计数器

88918

FunctionGHW

C语言通用数据结构_LinkedList

计数器

FunctionGHW

搜索

分类

博客链接

我的饭否

热门文章

最新评论

RSS