How to properly instantiate a MultiSet (created on my own) using Python

Question

I wanted to learn about Data Structures so I decided to create them using Python. I first created a Singly Linked List (which consists of two classes: the actual List and the Node). A List consists of Nodes (or can be empty). Each node had a "next" value. When I instantiated a list, it would look like this:

l = LinkedList([1,2])

and this was the sudocode for the init:

def __init__(self, item=None):
    head = None

    if a single item was given
        head = Node(item)
        head.next = None
    else if multiple items were given
        for i in item
            if head: # i is not the first item in the list
                new_head = Node(i)
                new_head.next = head
                head = new_head
            else: # i is the first item in the list
                head = Node(i)
                head.next = None

Maybe there is a flaw in the logic above, but hopefully you get how it works more or less. The key thing I noted here was that I did not use any list ([]) or array ({}) because I didn't need to.

Now, I am trying to create a MultiSet but I am stuck in the init part. It was simple for a Linked Lists because when I read articles on Linked Lists, all of the articles immediately mentioned a List class and a Node class (a List consists of a Node. a List has a head and a tail. a Node has a 'next' value). But when I read articles on MultiSets, they just mention that multisets are sets (or bags) of data where multiple instances of the same data are allowed.

This is my init for my multiset so far:

def __init__(self, items=None):
    self.multiset = []
    if items: # if items is not None
        try:
            for i in items: # iterate through multiple items (assuming items is a list of items)
                self.multiset.append(i)
        except: # items is only one item
            self.multiset.append(items)

I don't think I am on the right track though because I'm using a Python list ([]) rather than implementing my own (like how I did with a Linked List using Nodes, list.head, list.tail and node.next).

Can someone point me in the right direction as to how I would create and instantiate my own MultiSet using Python (without using existing Python lists / arrays)? Or am I already on the right track and am I supposed to be using Python lists / arrays when I am creating my own MultiSet data structure?

Answer 1

It looks like you're conflating two things:

• data structures - using Python (or any other language, basically), you can implement linked lists, balanced trees, hash tables, etc.

• mapping semantics - any container, but an associative container in particular, has a protocol: what does it do when you insert a key that's already in it? does it have an operation to access all items with a given key? etc.

So, given your linked list, you can certainly implement a multiset (albeit with not that great performance), because it's mainly a question of your decision. One possible way would be:

• Upon an insert, append a new node with the key

• For a find, iterate through the nodes; return the first key you find, or None if there aren't any

• For a find_all, iterate through the nodes, and return a list (or your own linked-list, for that matter), of all the keys matching it.

---

Similarly, a linked-list, by itself, doesn't dictate if you have to use it as a set or a dictionary (or anything else). These are orthogonal decisions.