Ask coding questions

← Back to all posts
[ C ] Most efficent way to implement dict
h
Coder100 (16804)

Most efficent way to implement dict

If you couldn't tell by the title (I think C is the only language savage enough to not have dicts, but for a good reason!), I have decided that dicts will look something like:

const char* my_dict[][] = {
  { "key", "2" },
  { "other key", "4" },
  { "imagine being able to duplicate keys successfully", "8" },
  { "key", "10" },
  { "as you can see that key will never be reached", "12" },
  NULL // sort of like a \0
};

Because there is no way to actually have mixed values (maybe union, but I think that's C), I will just manually convert to int values using sscanf (xD)

k time for the question...

Question

Retrieving keys in this dict will get slower as your keys are last. I think you guys describe this as O(n). Is this standard speed? Is there a faster search than:

int i = 0;
const char* search = "key";

while (my_dict[i++] != NULL) {
  if (my_dict[0] == search) {
    break; // I would actually return an array (probably setting it to some mem address)
  }
}

ok thanks
and because you guys don't have discord,
@DynamicSquid @fuzzyastrocat
finlay where are you :(

Comments
hotnewtop
fuzzyastrocat (1510)

The point of a dict is to provide O(1) lookup speed. Yes, constant time. Here's my standard hastable (dict) implementation — it uses 100 hash buckets and then uses a linked list from each one to handle overlap.

hash.h:

#ifndef browns_h
#define browns_h

struct hash_list_node {
  struct hash_list_node* next;
  char* name;
  char* value;
};

#define HASHSIZE 101
typedef struct hash_list_node* hashtab[HASHSIZE];

struct hash_list_node* hash_lookup(hashtab, char*);
struct hash_list_node* hash_insert(hashtab, char*, char*);
struct hash_list_node* hash_remove(hashtab, char*);
hashtab*               clone_hash (hashtab);

#endif

hash.c:

#include <stdlib.h>
#include <string.h>

#include "hash.h"

unsigned hash(char* s) {
  unsigned hashval;
  for (hashval = 0; *s != '\0'; s++)
    hashval = *s + 31 * hashval;
  return hashval % HASHSIZE;
}

struct hash_list_node *hash_lookup(hashtab h, char* s)
{
    struct hash_list_node* np;
    for (np = h[hash(s)]; np != NULL; np = np->next)
      if (strcmp(s, np->name) == 0)
        return np; /* found */
    return NULL; /* not found */
}

char* dupstr(char* s) { // ignore collision with POSIX
  char* p;
  p = (char *) malloc(strlen(s) + 1);
  if (p != NULL)
      strcpy(p, s);
  return p;
}

struct hash_list_node* hash_insert(hashtab h, char* name, char* defn)
{
    struct hash_list_node* np;
    unsigned hashval;
    if ((np = hash_lookup(h, name)) == NULL) {
      np = (struct hash_list_node *) malloc(sizeof(*np));
      if (np == NULL || (np->name = dupstr(name)) == NULL)
        return NULL;
  
      hashval = hash(name);
      np->next = h[hashval];

      h[hashval] = np;
    }

    np->value = dupstr(defn);

    return np;
}

struct hash_list_node* hash_remove(hashtab h, char* name) {
  struct hash_list_node* np;
  struct hash_list_node* prevp = NULL;
  for (np = h[hash(name)]; np != NULL; np = np->next) {
    if (strcmp(name, np->name) == 0) {
      if (prevp == NULL) {
        h[hash(name)] = np->next;
      }
      else prevp->next = np->next;
      free(np);
      break;
    }
    prevp = np;
  }
  
  return np;
}

hashtab* clone_hash(hashtab table) {
  hashtab* cloned = (hashtab*)calloc(1, sizeof(hashtab));
  for(int i = 0; i < HASHSIZE; i ++) {
    struct hash_list_node* lastnode = NULL;
    for(struct hash_list_node* np = table[i]; np != NULL; np = np->next) {
      struct hash_list_node* newnode = (struct hash_list_node*)malloc(sizeof(struct hash_list_node));
      memcpy(newnode, np, sizeof(struct hash_list_node));

      if(lastnode == NULL) {
        (*cloned)[i] = newnode;
        lastnode = (*cloned)[i];
      } else {
        lastnode->next = newnode;
        lastnode = lastnode->next;
      }
    }
  }

  return cloned;
}

Part of this is from the K&R C book — part of it is mine. You can use it like so:

hashtab my_hashtable;

hash_insert(my_hashtable, "x", "This is the x key!");
hash_lookup(my_hashtable, "x"); // => "This is the x key!"
hash_remove(my_hashtable, "x");

etc.

DynamicSquid (4621)

@fuzzyastrocat That looks like a singly linked list but with a key value. Is that correct? Also, how does the hash method work?

fuzzyastrocat (1510)

@DynamicSquid No, it's 101 singly linked lists and the one that is selected is determined by the hash of the string. That's why it can provide so good lookup time, because (most often) the hashes of strings will be different so it's looking through an entirely different linked list (which, most often, will be 1 node long).

The hash method is fairly simple, it has something to do with 31 being prime, but I took that out of the K&R book so I'm not the one to ask about its exact workings.

fuzzyastrocat (1510)

@xxpertHacker Whoops, mis-copied the remove function:

struct hash_list_node* hash_remove(hashtab h, char* name) {
  struct hash_list_node* np;
  struct hash_list_node* prevp = NULL;
  for (np = h[hash(name)]; np != NULL; np = np->next) {
    if (strcmp(name, np->name) == 0) {
      if (prevp == NULL) {
        h[hash(name)] = np->next;
      }
      else prevp->next = np->next;
      free(np);
      break;
    }
    prevp = np;
  }
  
  return np;
}
xxpertHacker (865)

@fuzzyastrocat Yup, that did the trick. Yay, the code is segfaulting now! (null pointer derefs)

fuzzyastrocat (1510)

@xxpertHacker Great! (I've never been happy about a segfault before)

elipie (379)

@fuzzyastrocat you also use browns when your using hashes EPIC :D

xxpertHacker (865)

Did Finlay give an example usage?

Coder100 (16804)

nope, he just took it from his k&r C book @xxpertHacker

Coder100 (16804)

do all of you just have programming in C lying around? @xxpertHacker

xxpertHacker (865)

@Coder100 Nope, I formally learned C++, never C. I never use C either so... yeah. I just know it from what I know about C++.

C + OOP = C++
thus
C++ - OOP = C

:)

xxpertHacker (865)

@Coder100 Aww, well, astro's is close enough, so I can figure it out.

xxpertHacker (865)

Dictionaries are intended to provide O(1) lookups and O(1) sets of arbitrary values, unlike an array that can only be indexed via numbers.
Furthermore, they're often mutable in size.

Iterating over an array will always be O(N) time, thus is not a good place to start.

Also, at this point, you might as well use a constructor function and go all out with OOP styled code.

Also, what you said was completely wrong

Because there is no way to actually have mixed values (maybe union, but I think that's C), I will just manually convert to int values using sscanf (xD)

C has unions, but that wouldn't help.

I was starting to setup a crappy implementation, but I don't have time to finish this, especially considering how others have already answered, and cookiebot's answer is already accepted.

#include <stdio.h>

void * malloc(unsigned long);

typedef unsigned short ushort;
typedef char const * key_t;
typedef ushort value_t;

typedef struct {
	const char * key;
	ushort value;
} item;

struct Dictionary;

typedef item (* const Dictionary_get_t)(struct Dictionary, const char *);
typedef struct Dictionary (* const Dictionary_set_t)(struct Dictionary, item);

struct Dictionary {
	item * list;
	ushort size;
	Dictionary_get_t get;
	Dictionary_set_t set;
};

item _Dictionary_get(struct Dictionary this, key_t key) {

	return (item) {
		.key = 0,
		.value = 0
	};
}

struct Dictionary _Dictionary_set(struct Dictionary this, item dict_item) {
	return this;
}

struct Dictionary _Dictionary_constructor(
	item * list,
	ushort length
) {
	item * temp_list = (item *)malloc(6 * sizeof(item));

	// memcpy or memmove instead
	for (ushort i = 0; i < length; ++i) {
		temp_list[i] = list[i];
	}

	struct Dictionary temp = {
		.list = temp_list,
		.size = length,
		.get = _Dictionary_get,
		.set = _Dictionary_set
	};

	return temp;
}

struct {
	struct Dictionary (* const constructor)(item* list, ushort length);
	struct {
		Dictionary_get_t get;
		Dictionary_set_t set;
	} prototype;
} Dictionary = {
	.constructor = _Dictionary_constructor,
	.prototype = {
		.get = _Dictionary_get,
		.set = _Dictionary_set
	}
};

// wierd macro replacement stuff
#define constructor(list) constructor( (list), sizeof (list) )

int main(void) {
	struct Dictionary my_dict = Dictionary.constructor(
		((item[5]) {
			{ "key", 2 },
			{ "other key", 4 },
			{ "imagine being able to duplicate keys successfully", 8 },
			{ "key", 10 },
			{ "as you can see that key will never be reached", 12 },
		})
	);

	ushort value = my_dict.get(my_dict, "key").value;

	printf("%u", value);

	return 0;
}
Coder100 (16804)

wow nice, if you completed it i would mark this @xxpertHacker

xxpertHacker (865)

@Coder100 Lol, well, just use structs with 2 items for constructing the array, that's all there is to take from it, and that it's OOP af.

But I'ma so steal Finlay's and merge with fuzzyastrocat's KR book modifications.

Maybe I'll finish it later today, but I got stuff to do till then.

fuzzyastrocat (1510)

@Coder100 Why no comment at all on my answer :(

@xxpertHacker A few things regarding your comment:

You need to include <stdlib.h> for malloc.

Also, at this point, you might as well use a constructor function and go all out with OOP styled code.

I'm not sure if OOP style code is best practice in C. It's clear that it wasn't the intention since it creates tons of unneeded code.

C has unions, but that wouldn't help.

Uh... no? The point of a union is to allow a type to have one of many types — so you could set up a simple "any-val" like so:

struct Value {
  enum {
    INT_VAL,
    FLOAT_VAL // etc etc
  } type;

  union {
    int int_val;
    float float_val;  // etc etc
  } as;
}

(I'm calling the union as so that you can go my_value.as.int_val.)

And now you could have the dictionary store values of type struct Value to allow it to store "anything" (any of the types that you've set up in the Value struct).

Coder100 (16804)

@fuzzyastrocat sorry i was too afraid to look at the spam that occured here

xxpertHacker (865)

@fuzzyastrocat

I'm not sure if OOP style code is best practice in C. It's clear that it wasn't the intention since it creates tons of unneeded code.

Lmao, that's exactly why I did it. You should never use OOP in C, the implementation was a joke.

And a union wouldn't allow you to do what he was saying couldn't be done:

const char* my_dict[][] = {
    { "key", "2" }
};

A struct allows you to do that:

struct item_t {
    char const * const key;
    unsigned value;
};

item_t my_dict[] = {
    { "key", 2 }
};
fuzzyastrocat (1510)

@xxpertHacker Oh lol, nice one. It got me good :D

Hm... now I'm trying to figure out what @Coder100 originally meant. I thought they meant "you can't store multiple types of values in the same container", but if they meant "you can't store two different types of values in the same list" then yes your answer is correct.

Coder100 (16804)

@fuzzyastrocat hmm I am still having some trouble understanding exactly what your process of a hashmap is.

xxpertHacker (865)

@fuzzyastrocat Now, who's to say that one can't use both at once like you had?

That code would be so dang ducktyped though, and wanting a dict<string, num> wouldn't be fun.

printf("%i", lookup(dict, "key0").value.as.int);
printf("%i", lookup(dict, "key1").value.as.int);
printf("%i", lookup(dict, "key2").value.as.int);

const int math = (lookup(dict, "key0").value.as.int + lookup(dict, "key2").value.as.int) / get_size(dict);
fuzzyastrocat (1510)

@xxpertHacker You could make it nicer by integrating the value directly into the hashmap, so you do lookup(...).as.int. And/or maybe you could do some macro magic.

But yeah, it's making it fairly ducktyped.

fuzzyastrocat (1510)

@Coder100 What do you mean by

your process of a hashmap

xxpertHacker (865)

@fuzzyastrocat

You need to include <stdlib.h> for malloc.

Well... umm... "stdlib.h" defines a key_t, so... yeah, I didn't wanna do that.

Also, your version (the KR book version), calls dupstr on every insertion and allocates new memory, which is unnecessary for string literals, wanna help me optimize that out if it's unnecessary?

https://repl.it/talk/ask/C-How-to-determine-if-a-string-is-in-rodata/78798

xxpertHacker (865)

@fuzzyastrocat My implementation will definitely return just the value, like expected of most maps.

fuzzyastrocat (1510)

@xxpertHacker You'll have to get malloc somehow...

My implementation was designed for langdev, where I need to clone the string. From what I know (and from what I can find online), there is no [standard] way to differentiate between constant string literals and other ones.

My solution would be to define another function which doesn't copy the string.

xxpertHacker (865)

@fuzzyastrocat I was just too lazy to rename key_t to something else.

Maybe I'ma make a no copy version, but yeah, I was thinking that we would need another function.

Also, can you please explain this line?

typedef struct hash_list_node* hashtab[HASHSIZE];

Is this creating an array type?

fuzzyastrocat (1510)

@xxpertHacker It's creating the type hashtab (the type of the hashtable itself), which is an array of struct hash_list_node*'s (pointers to linkedlists, which is how it deals with collisions) of size HASHSIZE (101 buckets).

xxpertHacker (865)

@fuzzyastrocat So, from there, every hashtable is that type?
Dang, that sounds memory intensive.

Also, why pointers?

fuzzyastrocat (1510)

@xxpertHacker Well yes, that's how a hashtable works (it's an array of "buckets").
Sounds memory intensive, but it's not that bad considering what a tiny fraction it is of the space it could take up.

Pointers because that points to the head of a linked list. Usually it will either point to NULL (bucket is empty) or it will point to a node whose next points to NULL (only one item in the bucket), but in the event of a collision the node will be added to the tail of the linkedlist.

Coder100 (16804)

wait you can do it without pointers? @xxpertHacker

Coder100 (16804)

what would happen if you reached max capacity? Would you just let the program segfault? @xxpertHacker

xxpertHacker (865)

@Coder100 When you hit max heap usage, malloc just returns NULL, lol.

xxpertHacker (865)

@Coder100 I think you can just use the structs directly.
@fuzzyastrocat is there any particular reason that we wouldn't want to?

I think it would take more memory though, as each struct is 3x the size of a pointer, because they each have 3 pointers themselves.

But the performance should improve, I think?
It would help avoid cache misses because there would be less look ups. Right now, the process is index array, dereference pointer, dereference pointer. It would change to index array, then dereference pointer.

fuzzyastrocat (1510)

@xxpertHacker You need a pointer since it needs to be a linked list to handle collisions.

xxpertHacker (865)

@fuzzyastrocat No, why item* hashtable[] instead of item table[]?

fuzzyastrocat (1510)

@xxpertHacker There's no guarantee that a list is even in the bucket (it could be empty), so how do you represent NULL if it's by-value?

fuzzyastrocat (1510)

@xxpertHacker No, that just initializes everything to zero (or whatever the "default" value is). That means there's still something there, but it has a name which is the NULL pointer and a value which is the NULL pointer (assuming the value is a string) and a next which is the NULL pointer. So that node still exists, it's just that everything in it is NULL. Which means you'd have to add in tons of edge cases to check that the name isn't NULL to figure out "should I overwrite or should I add to the chain". But then what happens when a user accidentally gives insert a null pointer name? Then it triggers the edge cases and weird stuff would happen.

xxpertHacker (865)

@fuzzyastrocat I'm not quite sure what you're saying. Why can't you just compare against the empty struct?

struct hash_list_node const NULL_NODE = {}; // block of zeroed memory (sizeof(void*) * 3)
// ...
if (input == NULL_NODE) {
    // all pointers are 0 (thus null), do something with that in mind
}

You already have to check for null pointers, it's literally the same.
A non-null pointer could point to an empty struct already, so it should be even simpler, as you no longer have to check for the null pointers, but null data.

fuzzyastrocat (1510)

@xxpertHacker Sure, that's fine. But that's where my second argument comes into play — what happens if the user (unknowingly, probably by accidentally freeing some malloc'ed memory or maybe being unable to malloc any more memory) gives NULL pointers? Then you trigger the edge handlers accidentally and weird stuff happens.

(Also, you'd have to add those handlers in a LOT of places)

Coder100 (16804)

where do you find these examples of hashmaps btw
I honestly think you just have the C programming language book just lying around...
@fuzzyastrocat

xxpertHacker (865)

@Coder100 Astro has the same K&R C book that Finlay had.

xxpertHacker (865)

@Coder100 Yes there are more than one... copy of the book.

xxpertHacker (865)

@Coder100 No clue. I don't have one. Never read it either.
From the examples I've seen, it's well outdated too.

xxpertHacker (865)

@Coder100 Hmm... I wouldn't hesitate to say "old," but "outdated," that I cannot say.

fuzzyastrocat (1510)

@Coder100 @xxpertHacker Guess what... I don't have the K&R C book! I've just found tidbits of it around the internet.

xxpertHacker (865)

@fuzzyastrocat Wait but...

Part of this is from the K&R C book — part of it is mine. You can use it like so:

And you don't even have one? Lol.

MocaCDeveloper (554)

Me and @realTronsi have made "dicts" in C before. It's not the actual {'key':'value'} but the concept of a dict is what we have made.
I am also creating "dicts" for my new language!

But yeah, we have made dynamic lists and dynamic arrays in C!

realTronsi (914)

@Coder100 wow imagine not responding to mine but responding to Moca :(

MocaCDeveloper (554)

@Coder100

Wdym? Like how did we do it?

realTronsi (914)

@Coder100 god theres so much spam I can't even scroll

MocaCDeveloper (554)

@realTronsi

Take the L my guy and go back to your noob mac desktop computer xDDD.

Jk

Coder100 (16804)

special thanks to an idiot @realTronsi

realTronsi (914)

@MocaCDeveloper when you say you don't have time to code but you're here chatting with Coder :(

MocaCDeveloper (554)

@realTronsi

Lol I know @Coder100 must be famous or something, everyone pings him when they either need help or they're showing off a project xD.

Imagine being @Coder100 and being pinged 500000000 times a day. I could never :C

I wonder if I am annoying him yet xD

realTronsi (914)

@Coder100 oh right you can't see anything. Anyways

we have a struct with two lists, a char list and a void list. The void list contains the pointers to the values while the char list contains the keys, simple

MocaCDeveloper (554)

@realTronsi

I am about to switch classes lol. I should be able to code my next class :D

realTronsi (914)

@MocaCDeveloper no the guy is spamming announcements and everything too

realTronsi (914)

@MocaCDeveloper @Coder100 also yes searching for keys is O(n) there isn't some fancy algorithm unless you decide to sort your list using quick sort and then using binary searching, which honestly won't shorten the time that much unless you have 1 million elements

realTronsi (914)

@MocaCDeveloper the technology teacher who teaches programming didn't know what fortran or assembly was smhhh

realTronsi (914)

@MocaCDeveloper you know that feeling when you know more programming than the school's programming teacher and you just want to die during their class

MocaCDeveloper (554)

@realTronsi

It's a good feeling but it gets boring after time

MocaCDeveloper (554)

@realTronsi

I walk into that class, I sit down and write code like a flippin boss and everyone else is figuring out how to drag the block code to finish the if statement xD

Then, when I get called to have my screen casted on the screen I write the code(like actually type it out) and I look back at the class and they're all like =O (ㆆ_ㆆ)

fuzzyastrocat (1510)

@realTronsi @Coder100 @MocaCDeveloper

also yes searching for keys is O(n)

That's incorrect, the point of a dict (hash table) is to provide O(1) lookup time.

realTronsi (914)

@fuzzyastrocat huh I'm talking about his while loop being O(n)

Hash tables require knowing the value, searching may be faster but other processes are slower

fuzzyastrocat (1510)

@realTronsi Uh no? Hash tables do exactly what your implementation does (which is O(n) time), but in O(1) time.

(And dicts (ie Python) are implemented as hashtables, and Coder100 asks about dicts.)

realTronsi (914)

@fuzzyastrocat too memory heavy imo and for other methods you'll have to use O(Log n) again

fuzzyastrocat (1510)

@realTronsi How is it too memory heavy? It's hardly any memory... that's why hashtables are the standard way implementing a dict. And what do you mean by

for other methods you'll have to use O(log n)

Just look at the wikipedia page for hash tables. Search: O(1). Insert: O(1). Delete: O(1).

MocaCDeveloper (554)

@realTronsi

Soon. I have something to do

MocaCDeveloper (554)

@realTronsi

I now have a test to take xD.
I will have available in like 40 minutes :/

xxpertHacker (865)

@realTronsi Legit how I was during my classes, the teacher couldn't understand my code, and it wasn't because it was weird garbage.

Coder100 (16804)

oh and btw for future people, special thanks to our savior finlay,

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
      hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
          return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}

char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
    if (p != NULL)
       strcpy(p, s);
    return p;
}
Jeydin21 (103)

@CarlosRosiles Why...why was this necessary...?

Jeydin21 (103)

@CarlosRosiles Umm...should I report you for spam

[deleted]
[deleted]

LOL THE GAUGE PERSON GOT BANNED

Coder100 (16804)

BOT COME OVER HERE SO I CAN MARK YOU AS CORRECT ANSWER
@coderbot100

[deleted]

@Coder100 LOLLL

Coder100 (16804)

Finlay says:

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
      hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
          return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}

char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
    if (p != NULL)
       strcpy(p, s);
    return p;
}
fuzzyastrocat (1510)

@Coder100 Oh dang, finlay beat me to it. Well still, check out my answer since it provides some other nice functions like key deletion and hashtable cloning.

The important thing to note is that this and my answer are the only answers here which provide an actual hashtable (dict) implementation. Everything else is a linked list implementation with a search operation, which will be a lot slower.