DEV Community: tartope

Doubly Linked List Series: Creating insert(), remove(), and reverse() methods with JavaScript

tartope — Sun, 29 Jan 2023 17:43:55 +0000

This post will conclude what I have learned about creating various methods within a Doubly Linked List. The methods that I will be discussing today build off of methods outlined in previous blog posts for this series. The previous methods needed to support the methods that I will be discussing today include get(), unshift() and shift(), and push() and pop(). Beginning with insert(), this method adds a node at a specified index. This method takes in two parameters (index and value), and calls on unshift(), push(), and get() methods to support it. Here is a visualization for creating this method:

Edge case 1: if the index is a negative number or greater than the length of the list, you can return false because that index is not valid.
Edge case 2: if the index is equal to zero, you can use the unshift() method to place a node at the start of the list.
Edge case 3: if the index is equal to the lists' length, you can use the push() method to place a new node at the end of the list.
If none of the above cases apply, then you can follow the steps outlined above.

Here is an example of code for an insert() method:

Next, the remove() method will remove a node at a specified index. This method takes one parameter (index) and makes use of shift() and pop() methods to support it. Below is a visualization for this method:

Edge case 1: if the index is a negative number or greater than or equal to the length, you can return undefined because the index passed is not valid.
Edge case 2: if the index is equal to zero, you can use the shift() method to remove a node from the start of the list.
Edge case 3: if the index is equal to the last index of the list, you can use the pop() method to remove the last node.
If none of the above cases apply, then you can follow the steps outlined above.

Here is an example of code for a remove() method:

Finally, this reverse() method will reverse a list in place and takes no parameters. This method works by swapping the head and tail, and changing the directions of the previous and next pointers. Below is an illustration:

Here is an example of code for a reverse() method:

The time complexity for these methods is O(1) constant time if insertion and removal occur at the start or end of the list because the number of operations remains the same. Otherwise, time complexity will be O(n) linear time because you will need to loop through the list to insert or remove at the middle, and the number of operations increases as the list's length increase. The reverse method is also O(n) linear time. Hopefully, others find this representation of the code helpful as it has been for me. There is so much to learn so please feel free to share comments or corrections if I have anything incorrect or missed anything. 🙂

Doubly Linked List Series: Creating get() and set() methods with JavaScript

tartope — Sun, 22 Jan 2023 14:09:19 +0000

This post will continue to build off of the previous blog on Doubly Linked List methods - linked here. Today I will share how I have learned to create get() and set() methods for a Doubly Linked List. Beginning with get(), this method accepts an index as a parameter and retrieves a node at a chosen position in the list. Since lists are not indexed, a counter will have to be used to find the wanted node. See an illustration below for this method:

Edge case: if the index is less than zero, or greater than or equal to the length of the list, return null. Otherwise, follow the steps listed above.

Here is an example of code for a get() method:

The method for set() is used to change the value of a node at a chosen position in the list. Set() accepts two parameters - an index to be found, and a value to be updated. Creating this method is a little easier because we can use the get() method created earlier to support this method. Below is an illustration:

Here is an example code for a set() method:

The time complexity for get() and set() methods in a Doubly Linked List is O(n) linear time because as the lists' length increases so does the number of operations. Please feel free to share comments or corrections if I got anything incorrect. In the next blog I will share what I have learned about creating insert(), remove(), and reverse() methods for Doubly Linked Lists.

Doubly Linked List Series: Creating shift() and unshift() methods with JavaScript

tartope — Mon, 09 Jan 2023 13:46:16 +0000

Building off of last week's blog on Doubly Linked List classes, push(), and pop() methods - linked here - today I will be discussing shift() and unshift() methods. Starting with shift(), this method does not take a parameter and removes the first node from the beginning of the list. Here is an illustration of a shift() method:

Edge case: you can account for an empty list, or has only one node. If neither of those cases applies, then follow the steps above.

Here is an example of code for a shift() method:

The method unshift() adds a node to the beginning of the list. Here is an illustration of this method:

Edge case: you can account for an empty list. If the list is not empty, then follow the steps mentioned above.

Here is an example of code for an unshift() method:

The time complexity for shift() and unshift() methods for a Doubly Linked List is O(1) constant time. The length of the list does not impact the number of steps to remove from the beginning or add to the beginning of the list.

In the next part of this series, I will share what I have learned about creating get() and set() methods for a Doubly Linked List.

Doubly Linked List Series: Node and Doubly Linked List Classes with push() and pop() methods using JavaScript

tartope — Sat, 31 Dec 2022 16:21:42 +0000

As I continue to study data structures and algorithms, I am finding that writing things out is helping to improve my understanding of data structures and a few ways to manipulate the data in them. I will use this series to discuss Doubly Linked Lists, and use illustration, followed by example code, to lay out my understanding of a few methods.

Doubly Linked Lists are similar to Singly Linked Lists. If you are looking for an explanation on Singly Linked Lists, you can take a look at my posts on that. One key difference with Doubly Linked Lists is that they have a pointer that references the previous node. Also, they take up more memory however that comes with more flexibility because you are not confined to traversing the list in one direction only.

Building a Node class for Doubly Linked Lists is similar to building a Node class for Singly Linked Lists and the only difference is adding a previous pointer. A node is an object with a key-value pair and will look like this: {value: value, next: null, prev: null}. Here is an illustration of nodes referencing each other:

Here is an example of code that builds the node:

A Doubly Linked List class creates the structure for the list. It includes the head, tail, and length properties. Here is an example of code that builds the Doubly Linked List:

These two classes are used to instantiate a list. Within the Doubly Linked List class, various methods can be written. I will share two methods: push() and pop(). When you are looking to add a node to the end of a list, you can create a push() method. This method takes a parameter to create a new node that is added to the end of the list. Here is an illustration of that method:

Edge case: you can account for an empty list. If it is not empty, then follow the steps mentioned above.

Here is an example code for a push() method:

A pop() method removes a node from the end of a Doubly Linked List. A parameter is not needed for this method. Below is an illustration:

Edge cases: account for if the list is empty, or has only one node. If neither of those cases applies, then follow the steps illustrated above.

Here is an example code for a pop() method:

The time complexity for push() and pop() methods in a Doubly Linked List will be O(1) constant time because the number of operations does not increase as the length of the list increase.

Next week I will share what I have learned about creating shift() and unshift() methods. As always, the learning process is ongoing, so feel free to share your comments if I got anything incorrect. 😀

Singly Linked List Series: Creating insert(), remove(), and reverse() methods with JavaScript

tartope — Sat, 17 Dec 2022 16:29:50 +0000

I will be wrapping up this Singly Linked List Series by sharing my understanding of creating insert(), remove(), and reverse() methods. Beginning with insert(), this method receives two parameters: index and value. This method adds a node at a specified index with the value passed. It returns true if the node was inserted; otherwise, it returns false. This method uses get(), unshift() and shift(), and push() and pop() methods to support it. See the previous Singly Linked List Series blog posts linked above to get an understanding of creating these methods. Let's start with a visualization for creating this method:

Edge case 1: if the index is a negative number or greater than the length of the list, you can return false because that index is not valid.
Edge case 2: if the index is equal to zero, you can use the unshift() method to place a new node at the beginning of the list.
Edge case 3: if the index is equal to the length of the list, you can use the push() method to place a new node at the end of the list.
If none of the above edge cases apply, you can follow the steps above.

Here is an example of code for an insert() method:

A remove() method will remove a node from a Singly Linked List at a specific index. This method accepts an index as a parameter. The visualization looks like this:

Edge case 1: if the index is a negative number or greater than or equal to the length, you can return undefined because that index is not valid.
Edge case 2: if the index is equal to zero, you can use the shift() method to remove a node from the beginning of the list.
Edge case 3: if the index is equal to the last index in the list, you can use the pop() method to remove a node from the end of the list.
Same as before, if none of the above edge cases apply, you can follow the steps above.

Here is an example of code for a remove() method:

Lastly, the reverse() method that I will share reverses the list in place. This method takes no parameters. See the steps and visualization below:

Here is an example of code for a reverse() method:

The time complexity of these insert(), remove(), and reverse() methods for a Singly Linked List are O(n) linear time because the number of operations increases as the lists' length increases.

Writing out the steps and drawing the visualizations really helped me better my understanding of creating methods for Singly Linked Lists, and my hope is that this is helpful to someone else, too. However, there is still so much more for me to learn, so feel free to share your comments or corrections if there is anything written above that is incorrect. 🙂

Singly Linked List Series: Creating get() and set() methods with JavaScript

tartope — Sat, 10 Dec 2022 18:03:13 +0000

One can create a number of methods to manipulate a Singly Linked List. Today, I will do my best to share what I understand about creating get() and set() methods. A get() method receives an index parameter and retrieves a node at that particular index. Since Singly Linked Lists are not indexed like arrays, one must create a counter to keep track of "indexes." Let's start with a visualization for creating this method:

Edge case: if the index is a negative number or greater than or equal to the length of the list, you can return undefined because that index does not exist. Otherwise, follow the steps above.

Here is an example of code for a get() method:

A set() method changes the value of a particular node. This method accepts index and value parameters. The visualization looks like this:

Here is an example of code for a set() method:

The time complexity of a get() and set() method for a Singly Linked List is O(n) linear time because the number of operations increases as the lists' length increases. As I learn more about these topics, the methods become a bit more complex. Share your comments or corrections if there is anything written above that is incorrect. Next week, I will share what I have learned about creating insert() and remove() methods.

Singly Linked List Series: Creating shift() and unshift() methods with JavaScript

tartope — Sat, 03 Dec 2022 16:55:40 +0000

While continuing to learn data structures and algorithms, I want to continue to share my understanding in case others find it helpful. Today, I want to share how to create shift() and unshift() methods. A shift() method removes the first node from the beginning of a Singly Linked List. Here is my visualization for creating a shift() method:

Edge case: you can account for an empty list. If it is not empty, then follow the steps mentioned above. A second edge case is to redefine the head and tail if the list becomes empty after multiple shift() method applications.

Here is an example of code for a shift() method:

An unshift method adds a node to the beginning of a Singly Linked List. Here is my visualization for creating an unshift() method:

Edge case: you can account for an empty list. If the list is not empty then follow the steps mentioned above.

Here is an example of code for an unshift() method:

The time complexity of shift() and unshift() methods for a Singly Linked List is O(1). No matter the length of the list, it takes the same number of steps to remove from the beginning or add to the beginning of the list.

In the next part of this series, I will share what I have learned about creating a get() method to grab a chosen node, and a set() method to change the value of a chosen node.

Singly Linked List Series: Creating push() and pop() methods with JavaScript

tartope — Sat, 26 Nov 2022 14:46:40 +0000

Adding a node to the end of a Singly Linked List and removing a node from the end of a Singly Linked List is less difficult once you visually map out what needs to happen. Here is my visualization for creating a push() method that adds a node to the end of a Singly Linked List:

Edge case: you can account for an empty list. If it is not empty then follow the steps mentioned above.

Here is an example of code for a push() method:

Here is my visualization for creating a pop() method that removes a node from the end of a Singly Linked List:

Edge case: you can account for the list becoming empty. If it becomes empty then follow the steps in the example code below.
Here is an example of code for a pop() method:

Mapping out these visualizations helped increase my understanding of creating push() and pop() methods for Singly Linked Lists. Hopefully, others will find this helpful too. Feel free to share your corrections if I got anything wrong.😀

Singly Linked List Series: Node and Singly Linked List Classes with JavaScript

tartope — Sat, 19 Nov 2022 13:45:10 +0000

While currently studying data structures and algorithms, I thought this would be a good place to "think out loud" and possibly help others along the way. I have been working on understanding Singly Linked Lists and here is what I have learned when it comes to building a Node class and a Singly Linked List class. Feel free to share your corrections if I get anything incorrect.

A Singly Linked List is a linear data structure. It is composed of nodes; each node points to the next node while the last node points to null. Unlike arrays, Singly Linked Lists are non-contiguous in memory, so new nodes can be added wherever there is space in memory. Arrays are contiguous in memory so the elements must be stored right next to each other. Arrays have a fixed size. In order to add elements to an array, you must copy all the elements into another place in memory with more space. Also, Singly Linked Lists are good at insertion and deletion at the beginning (the head), and insertion at the end (the tail). It takes fewer operations to do this, so the time complexity is O(1) constant time. However unlike arrays, Singly Linked Lists do not have indices, and random access of a node is not allowed.

My understanding of the Node class is that it builds the node's structure. A node is basically an object with a key/value pair: {value: value, next: null}. Nodes are connected via their next values. The next value points to the next node. Here is an example of a node pointing to the next node:

Here is an example of code for a Node class that constructs the node:

A Singly Linked List class builds the list's structure with the head, tail, and length. Here is an example of code for a Singly Linked List class that constructs the list:

Using these two classes, a Singly Linked List can be instantiated and built with nodes using the Node class. Within the Singly Linked List, various methods can be written to access and manipulate the list.

In the next part of this series, I will share what I have learned about adding nodes to the end of a list and removing nodes from the end of a list.

Rails: A serializer for your serializer?

tartope — Sat, 07 May 2022 21:46:43 +0000

Getting used to serializers was tricky for me when I first learned of them. Then came custom serializers. 😑 I now think of them as a serializer for your serializer. Silly, I know. A custom serializer can be used to streamline the JSON data that is returned. Example: The models are director--< movies--< reviews. The return needs to be JSON data for director that includes the streamlined data for all movies of that director. Create a new serializer (DirectorMovieSerializer) and include only the attributes of movie that you want to be returned. Don't forget to add the has_many :movies relationship to your DirectorSerializer, and explicitly tell the DirectorSerializer to use the new serializer instead. See the code below:

DirectorSerializer:

Add DirectorMovieSerializer:

JSON data to be returned:

The JSON data returned should be the director data and the streamlined movie data. This made more sense to me when I started playing around with the code, so give it a try. 😀

Using Serializers in Rails

tartope — Fri, 06 May 2022 23:42:08 +0000

Serializers can be used to customize JSON data for a single model. However, they can also be used to handle associations between multiple models. The has_many and belongs_to Active Record macros can assist.

To use a serializer with a one-to-many association, add the belongs_to macro to the corresponding serializer. Example: there are three models, episode--< appearances >--guests. When the JSON data for appearances is returned, I want to include the data for episode and guest. Since the relationships have been established in the model, I can include the same has_one :episode and has_one :guest relationship in the corresponding serializer. Therefore, when the JSON data for appearance is returned, it will include the data for episode and guest.

The same can be used with many-to-many associations. Example: I want the JSON data to include guests along with data for episodes. Including the has_many :guests relationship in the corresponding episode serializer will return JSON data with the episode, and guests.

What helped me understand these concepts the most was seeing them in action. Practice coding different serializers to see the JSON data that is returned.

Ruby and Active Record Associations

tartope — Thu, 14 Apr 2022 19:09:22 +0000

Active Record Associations come in handy when working with multiple models (tables) in your database. Having a good understanding of Active Record will make working with data across multiple models easier. Associations you can build are one-to-many and many-to-many associations.

When you have two models a one-to-many association can be used. For example, you have a database with the models: Games and Reviews. In this case, you can imagine that a game can have many reviews, and a review will belong to one game. The Review model will read as "belongs_to :game", and the Games model will read as "has_many :reviews".

When working with multiple models a many-to-many association is used here. Now imagine you have a database with the models: Games, Reviews, and Users. A user can have many reviews and be associated with many games through their reviews. The Review model will read as "belongs_to :game", and "belongs_to :users". The Games model will read as "has_many :reviews" and include "has_many :users, through: :reviews". The Users model will read as "has_many :reviews" and include "has_many :games, through: :reviews".

Naming is important when using Active Record associations so be careful to use singular vs. plural naming conventions.