If you are a software engineer or studying to become a software engineer, then you have probably come across these Computer Science concepts - Data Structures and Algorithms.

What are Data Structures and Algorithms?

Data Structures and Algorithms called DSA for short, are two important related concepts in Computer Science and Software Engineering.

Data Structures are simply methods of organizing or holding data in a virtual system. Algorithms are step-by-step instructions given to a computer to execute by collecting some input in order to produce a targeted output.

While certain software engineers have a theory that studying DSAs is not so important as they believe there are only a little or no applications of DSAs in real-life software, understanding DSAs will improve your ability to solve coding problems more efficiently as we will see in this application.

What is a LinkedList?

A LinkedList is a data structure that holds a collection of nodes that are connected to each other. A node in a LinkedList is an independent object that holds two important values at the least; the value of the node and a pointer that connects it to another node.

A Basic LinkedList starts with a node, called HEAD node, that is connected to the next node by a pointer value except the last node, whose pointer value is null.

There are 3 basic types of LinkedLists:

• Singly LinkedList

• Doubly LinkedList

• Circular LinkedList

In this application, we will use the Doubly and Circular LinkedLists.

Background of the Secret VAL Match-Making Website.

This program is a secret VAL matching website. The aim of the software was to match my college students to exchange gifts on valentine’s day.

The website is aimed at matching opposite genders (male and female). The caveat to that plan is that there would most likely be an unequal amount of males and females.

That was exactly what happened. The website got a total of 1292 registrations, 991 of the registrations were males and only 301 were females.

Match-Making Algorithm with LinkedList:

Before thinking about the algorithm, we need to have a representation of the students. So, let’s create a model like this:

Student:

• fullname: string

• phoneNumber: string

• department: string

• gender: string

• year: string

• matchedFrom: Student

• matchedTo: Student.

With a model like that, the basic algorithm to match males to females is quite straightforward. With the matchedTo and matchedFrom fields, one male can connect to a female and the same female can connect to the same male. And we can do that with the Circular LinkedList Data Structure.

In a Circular LinkedList, the last node points back to a previously reached node in the LinkedList, most times it points back to the first node, hence the name, CIRCULAR.

See how that looks like a Circular, Doubly LinkedList?

Cross Gender Algorithm:

START

• FILTER ALL students that are males

• FILTER ALL students that are females

• LET len_males be the length of all males

• LET len_females be the length of all females

• LET min_length be the minimum length between len_males and len_females

• LET i = 0

• WHILE i < len_males;

• UPDATE females[I].matchedTo to males[i]

• UPDATE females[I].matchedFrom to males[i]

• UPDATE males[I].matchedTo to females[i]

• UPDATE males[I].matchedFrom to females[i]

• UPDATE i to (i+1)

• END WHILE

END

With this algorithm, we can successfully match all 301 females to 301 males.

Here's an implementation example in Python/Django:

However, this creates a problem for the remaining 691 males. We can decide to match them to each other as well, match one male to another male. That would have worked if it was an even number but with this odd number of males remaining using the same algorithm above, will always leave one male unmatched.

We need to look for a better algorithm to make sure that every student is matched, even if we have to match them to the same gender. It’s only a gift-exchanging program so, why not?

So, with the matchedTo and matchedFrom fields, we can connect every male to the next male and then connect the last male back to the first male.

Same Gender Algorithm:

START

• FILTER ALL remaining unmatched students

• CREATE variable “prev_student” and initialize to null

• CREATE variable “first_student” and initialize to null

• FOR student in unmatched students

• IF first_student is null

• UPDATE first_student to student

• END IF

• IF prev_student is not null

• UPDATE prev_student.matchedTo to student

• UPDATE student.matchedFrom to prev_student

• END IF

• UPDATE prev_student to student

• END FOR

• UPDATE prev_student.matchedTo to first_student

• UPDATE first_student.matchedFrom to prev_student

END

This part of the algorithm is only needed after all the available females have been matched with males, that way it will always leave only students of one gender left to match.

An Implementation in code:

Testing the Algorithm

5 females and 2 males:

The first algorithm will match 2 males to 2 females.

The second algorithm can match all the remaining 3 females to themselves. Everyone gets a gift, the algorithm works!

23 males and 10 females:

The first algorithm will match 10 males to 10 females.

The second algorithm can match all the remaining 13 males to themselves. Everyone gets a gift, the algorithm works!

40 males and 39 females:

The first algorithm will match 39 males to 39 females.

But how can we cater to just 1 person in the second algorithm?

Well, we know that every other student has been matched with an opposite gender, so, unfortunately, we will have to break one of the 39 fancy matches we initially created.

Luckily for us, we created the first algorithm using the Doubly LinkedList data structure. So, all we have to do is grab one of the matches above and convert it into a 3-node Circular LinkedList.

This has been interesting so far and it was a very fun project to build for the valentine's season on campus.

For more details and applications of LinkedLists, see the resources below:

What Are Applications of LinkedList? - https://www.scaler.com/topics/application-of-linked-list/

Applications of linked list data structure - https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/

Types of Linked Lists in Data Structures - https://www.simplilearn.com/tutorials/data-structure-tutorial/types-of-linked-list