FunctionGHW

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

C语言通用数据结构_LinkedList

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

此链表为双向链表(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

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 do i earn $200 per day online in 2020

لی ویوسوہ ہو یار 说:
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

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. Visa de India

<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

登录 *


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