Skip to content

ihiiro/singly_linked_list

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

45 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

# ░██████╗██╗███╗░░██╗░██████╗░██╗░░░░░██╗░░░██╗░░░░░░
# ██╔════╝██║████╗░██║██╔════╝░██║░░░░░╚██╗░██╔╝░░░░░░
# ╚█████╗░██║██╔██╗██║██║░░██╗░██║░░░░░░╚████╔╝░█████╗
# ░╚═══██╗██║██║╚████║██║░░╚██╗██║░░░░░░░╚██╔╝░░╚════╝
# ██████╔╝██║██║░╚███║╚██████╔╝███████╗░░░██║░░░░░░░░░
# ╚═════╝░╚═╝╚═╝░░╚══╝░╚═════╝░╚══════╝░░░╚═╝░░░░░░░░░
# ██╗░░░░░██╗███╗░░██╗██╗░░██╗███████╗██████╗░░░░░░░██╗░░░░░██╗░██████╗████████╗
# ██║░░░░░██║████╗░██║██║░██╔╝██╔════╝██╔══██╗░░░░░░██║░░░░░██║██╔════╝╚══██╔══╝
# ██║░░░░░██║██╔██╗██║█████═╝░█████╗░░██║░░██║█████╗██║░░░░░██║╚█████╗░░░░██║░░░
# ██║░░░░░██║██║╚████║██╔═██╗░██╔══╝░░██║░░██║╚════╝██║░░░░░██║░╚═══██╗░░░██║░░░
# ███████╗██║██║░╚███║██║░╚██╗███████╗██████╔╝░░░░░░███████╗██║██████╔╝░░░██║░░░
# ╚══════╝╚═╝╚═╝░░╚══╝╚═╝░░╚═╝╚══════╝╚═════╝░░░░░░░╚══════╝╚═╝╚═════╝░░░░╚═╝░░░
# Author: Hiro (ihiiro)
# Email: [email protected]
# License: MIT
# Start: 2023
# Update: 2023

Memory safety: excerpt from valgrind output:

==4699== All heap blocks were freed -- no leaks are possible

Benchmark environment:

Operating System: Kali GNU/Linux Rolling x86_64

Hostname: HP 255 G3 Notebook PC

Kernel: 6.4.0-kali3-amd64

Shell: zsh 5.9

CPU: AMD E1-2100 APU (2 cores) @ 1.0 GHz

GPU: AMD ATI Radeon HD 8210

Memory: 3364 MiB total

Calculated using: time.h's clock() and CLOCKS_PER_SEC

Benchmark for singly linked list

new_list() (1,000,000 calls)                                    0.032957s
append() (1,000,000 calls)                                      0.480136s
traverse() (traverse 1,000,000 nodes, process=strllen)          0.098582s
free_sll() (free 1,000,000 nodes)                               0.134015s

API

typedef struct	sll_t
{
	char			*payload;
	struct sll_t	*next;
}	sll_t;

typedef struct  sll_headnode_t
{
	sll_t			*next;
	sll_t			*tail;
	int				length;
	int				size_in_bytes;
}	sll_headnode_t;
sll_headnode_t	new_list(void);

list constructor, here for your own safety, returns an sll_headnode_t.

void	traverse(sll_headnode_t *list, void (*process)(sll_t *));

traverses the list, applying process to each node.

void	append(sll_headnode_t *list, char *payload);

appends a new node to the list.

void	free_sll(sll_headnode_t *list);

frees the entire list.