Tech-n-law-ogy

Outputting Markdown from Jekyll using hooks

One of the things I most enjoy about Jekyll1 is writing my blog posts in Markdown. I love not worrying about HTML and just letting Jekyll generate it for me when a post is published. Using Liquid tags directly in Markdown is also helpful, as I can define sitewide or page-specific variables and then replace them during site generation. This is a really useful capability that I wanted to take advantage of to output Markdown for use in other sites. Places like Medium and dev.to allow you to post Markdown articles, so I thought repurposing the Markdown I used in Jekyll would make crossposting to those sites easier.

I assumed that there would be a property on the page variable that would give me access to the rendered Markdown, but I was wrong. This began a long journey through relatively undocumented corners of the Jekyll plugin ecosystem. I’m sharing that journey here in the hopes that others won’t have to go through the same frustrating experience.

An introduction to Jekyll plugins

I was relatively unfamiliar with the Jekyll plugin system before trying to figure out how to get the rendered Markdown for a post. Jekyll supports a number of different plugin types2. These plugin types affect Jekyll directly:

  • Generators - plugins that create files. While it’s not required that generators create files, this is the most frequent use case. Plugins like jekyll-archives use generators to create files that wouldn’t otherwise exist.
  • Converters - plugins that convert between text formats. Jekyll’s default of converting Markdown files into HTML is implemented using a converter. You can add support for other formats to be converted into HTML (or any other format) by creating your own converter.
  • Hooks - plugins that listen for specific events in Jekyll and then perform some action in relation to the events.

There are also two plugin types that are used primarily with Liquid:

  • Tags - create a new tag in the format {% tagname %} for use in your templates.
  • Filters - create a new filter that you can use to transform input, such as {{ data | filter }}

There is also a command plugin type that allows you to create new commands to use with the jekyll command line tool. The jekyll build command is implemented using this plugin type.

Designing the solution

My goal was to get the Liquid-rendered Markdown content (so all data processing was complete) for each post into a page property so that I could output that content into a JSON file on my server. That JSON file would then be fetched by an AWS Lambda function that crossposted that content to other locations. I didn’t need to generate any extra files or convert from one format to another, so it seemed clear that using a hook would be the best approach.

Hooks are basically event handlers in which you specify a container and the event to listen to. Jekyll passes you the relevant information for that event and you can then perform any action you’d like. There are four containers you can use with hooks:

  • :site - the site object
  • :page - the page object for each non-collection page
  • :post - the post object for each blog post
  • :document - the document object for each document in each collection (including blog posts and custom collections)

Because I wanted this solution to work for all collections in my site, I chose to use :document as an easy way to make the same change for all collection types.

There were two events for :document that immediately seemed relevant to my goal:

  • :pre_render - fires before the document content is rendered
  • :post_render - fires after the document content is rendered but before the content is written to disk

It seemed clear that getting the Markdown content would require using the :pre_render event, so I started by using this setup:

Jekyll::Hooks.register :documents, :pre_render do |doc, payload| # code goes here end

Each hook is passed its target container object, in this case doc is a document, and a payload object containing all of the relevant variables for working with the document (these are the variables available inside of a template when the document is rendered).

The :document, :prerender hook is called just before each document is rendered, meaning you don’t need to worry about looping over collections manually.

The catch: Rendering doesn’t mean what you think it means

I figured that the content property inside of a :document, :pre_render hook would contain the Liquid-rendered Markdown instead of the final HTML, but I was only half correct. The content property actually contains the unprocessed Markdown that still contains all of the Liquid variables. It turns out that “prerender” means something different than I thought.

The lifecycle of the content property for a given document in Jekyll looks like this3:

  1. The content property contains the file content with the front matter removed (typically Markdown)
  2. :pre_render hook fires
  3. The content property is rewritten with Liquid tags rendered (this is what Jekyll internally refers to as rendering)
  4. The content property is rewritten after being passed through a converter (this is what Jekyll internally refers to as converting)
  5. The :post_render hook fires

While Jekyll internally separates rendering (which is apply Liquid) and converting (the Markdown to HTML conversion, for example), the exposed hooks don’t make this distinction. That means if I want Markdown content with Liquid variables replaced then I’ll need to get the prerendered Markdown content and render it myself.

The solution

At this point, my plan was to create a pre_render hook that did the following:

  1. Retrieved the raw content for each document (contained in doc.content)
  2. Render that content using Liquid
  3. Store the result in a new property called unconverted_content that would be accessible inside my templates

I started out with this basic idea of how things should look:

Jekyll::Hooks.register :documents, :pre_render do |doc, payload| # get the raw content raw_content = doc.content # do something to that raw content rendered_content = doSomethingTo(raw_content) # store it back on the document doc.rendered_content = rendered_content end

Of course, I’m not very familiar with Ruby, so it turned out this wouldn’t work quite the way I thought.

First, doc is an instance of a class, and you cannot arbitrarily add new properties to objects in Ruby. Jekyll provides a data hash on the document object, however, that can be used to add new properties that are available in templates. So the last line needs to be rewritten:

Jekyll::Hooks.register :documents, :pre_render do |doc, payload| # get the raw content raw_content = doc.content # do something to that raw content rendered_content = doSomethingTo(raw_content) # store it back on the document doc.data['rendered_content'] = rendered_content end

The last line ensures that page.rendered_content will be available inside of templates later on (and remember, this is happening during pre_render, so the templates haven’t yet been used).

The next step was to use Liquid to render the raw content. To figure out how to do this, I had to dig around in the Jekyll source4 as there wasn’t any documentation. Rendering Liquid the exact same way that Jekyll does by default requires a bit of setup and pulling in pieces of data from a couple different places. Here is the final code:

Jekyll::Hooks.register :documents, :pre_render do |doc, payload| # make some local variables for convenience site = doc.site liquid_options = site.config["liquid"] # create a template object template = site.liquid_renderer.file(doc.path).parse(doc.content) # the render method expects this information info = { :registers => { :site => site, :page => payload['page'] }, :strict_filters => liquid_options["strict_filters"], :strict_variables => liquid_options["strict_variables"], } # render the content into a new property doc.data['rendered_content'] = template.render!(payload, info) end

The first step in this hook is to create a Liquid template object. While you can do this directly using Liquid::Template, Jekyll caches Liquid templates internally when using site.liquid_renderer.file(doc.path), so it makes sense to use that keep the Jekyll build as fast as possible. The content is then parsed into a template object.

The template.render() method needs not only the payload object but also some additional information. The info hash passes in registers, which are local variables accessible inside of the template, and some options for how liquid should behave. With all of that data ready, the content is rendered into the new property.

This file then needs to be placed in the _plugins directory of a Jekyll site to run each time the site is built.

Accessing rendered_content

With this plugin installed, the Markdown content is available through the rendered_content property, like this:

{{ page.rendered_content }}

The only problem is that outputting page.rendered_content into a Markdown page will cause all of that Markdown to be converted into HTML. (Remember, Jekyll internally renders Liquid first and then the result is converted into HTML.) So in order to output the raw Markdown, you’ll need to either apply a filter that prevents the Markdown-to-HTML conversion from happening, or use a file type that doesn’t convert automatically.

In my case, I’m storing the Markdown content in a JSON structure, so I’m using the jsonify filter, like this:

--- layout: null --- { {% assign post = site.posts.first %} "id": "{{ post.url | absolute_url | sha1 }}", "title": {{ post.title | jsonify }}, "date_published": "{{ post.date | date_to_xmlschema }}", "date_published_pretty": "{{ post.date | date: "%B %-d, %Y" }}", "summary": {{ post.excerpt | strip_html | strip_newlines | jsonify }}, "content_markdown": {{ post.rendered_content | jsonify }}, "content_html": {{ post.content | jsonify }}, "tags": {{ post.tags | jsonify }}, "url": "{{ post.url | absolute_url }}" }

Another option is to create a rendered_content.txt file in the _includes directory that just contains this:

{{ page.rendered_content }}

Then, you can include that file anywhere you want the unconverted Markdown content, like this:

{% include "rendered_content.txt" %} Conclusion

Jekyll hooks are a useful feature that let you interact with Jekyll while it is generating your site, allowing you to intercept, modify, and add data along the way. While there aren’t a lot of examples in the wild, the concept is straightforward enough that with a few pointers, any programmer should be able to get something working. The biggest stumbling point for me was the lack of documentation on how to use Jekyll hooks, so I’m hoping that this writeup will help others who are trying to accomplish similar tasks in their Jekyll sites.

To date, I’ve found Jekyll to be extremely versatile and customizable. Being able to get the Liquid-rendered Markdown (even though it took a bit of work) has made my publishing workflow much more flexible, as I’m now more easily able to crosspost my writing on various other sites.

References
  1. Jekyll 

  2. Jekyll Plugins 

  3. Jekyll Order of Interpretation 

  4. Jekyll renderer.rb 

Categories: Tech-n-law-ogy

Computer science in JavaScript: Circular Doubly-linked lists

In my previous post, I discussed what changes are necessary to turn a singly linked list into a doubly linked list. I recommend reading that post before this one (if you haven’t already). This post is about modifying a doubly linked list (also called a linear doubly linked list) in such a way that the last node in the list points to the first node in the list, effectively making the list circular. Circular doubly linked lists are interesting because they allow you to continuously move through list items without needing to check for the end of the list. You may encounter this when creating playlists or round-robin distribution of traffic to servers.

It is possible to create a circular singly linked list, as well. I won’t be covering circular singly linked lists in this blog post series, however, you can find source code for a circular singly linked list in my GitHub repo, Computer Science in JavaScript.

The design of a circular doubly linked list

The nodes in a circular doubly linked list are no different than the nodes for a linear doubly linked list. Each node contains data and pointers to the next and previous items in the list. Here is what that looks like in JavaScript:

class CircularDoublyLinkedListNode { constructor(data) { this.data = data; this.next = null; this.previous = null; } }

You can then create a circular doubly linked list using the CircularDoublyLinkedListNode class like this:

// create the first node const head = new CircularDoublyLinkedListNode(12); // add a second node const secondNode = new CircularDoublyLinkedListNode(99); head.next = secondNode; secondNode.previous = head; // add a third node const thirdNode = new CircularDoublyLinkedListNode(37); secondNode.next = thirdNode; thirdNode.previous = secondNode; // point the last node to the first thirdNode.next = head; head.previous = thirdNode;

The head of the list and subsequent nodes in the list are created the same way as in a linear doubly linked list. The only difference is the last step where the last node’s next pointer is set to head and the head node’s previous pointer is set to the last node. The following image shows the resulting data structure.

Traversing a circular doubly linked list is a bit different than a linear doubly linked list because following next pointers alone will result in an infinite loop. For example, this is an infinite loop:

let current = head; // infinite loop: `current` is never `null` while (current !== null) { console.log(current.data); current = current.next; }

In some cases you will want to continue iterating over the loop forever, but that typically does not happen in the context of a loop as in this code. In other cases, you’ll want to iterate over each node in the loop until the last node is found. To do that, you’ll need to check to see when current is head, which means you’re back at the beginning of the loop. However, simply swapping null for head in the previous example results in the loop not executing at all:

let current = head; // loop is skipped: `current` is already `head` while (current !== head) { console.log(current.data); current = current.next; }

The problem here is that current started out equal to head and the loop only proceeds when current is not equal to head. The solution is to use a post-test loop instead of a pre-test loop, and in JavaScript, that means using a do-while loop:

let current = head; if (current !== null) { do { console.log(current.data); current = current.next; } while (current !== head); }

In this code, the check to see if current is equal to head appears at the end of the loop rather than at the start. To ensure that the loop won’t start unless current isn’t null, an if statement typically must preceed the do-while loop (you no longer have the pre-test of a while loop to cover that case for you). The loop will proceed until current is once again head, meaning that the entire list has been traversed.

Also similar to linear doubly linked lists, you can traverse the nodes in reverse order by starting from the last node. Circular doubly linked lists don’t separately track the list tail because you can always access the tail through head.previous, for example:

let current = head.previous; if (current !== null) { do { console.log(current.data); current = current.previous; } while (current !== head.previous); } The CircularDoublyLinkedList class

The CircularDoublyLinkedList class starts out looking a lot like the DoublyLinkedList class from the previous article with the exception that there is no tail property to track the last node in the list:

const head = Symbol("head"); class CircularDoublyLinkedList { constructor() { this[head] = null; } }

The primary differences between a linear and circular doubly linked list have to do with the methods for adding, removing, and traversing the nodes.

Adding new data to the list

The same basic algorithm for adding data is used for both linear and circular doubly linked lists, with the difference being the pointers that must be updated to complete the process. Here is the add() method for the CircularDoublyLinkedList class:

class CircularDoublyLinkedList { constructor() { this[head] = null; } add(data) { const newNode = new CircularDoublyLinkedListNode(data); // special case: no items in the list yet if (this[head] === null) { this[head] = newNode; newNode.next = newNode; newNode.previous = newNode; } else { const tail = this[head].previous; tail.next = newNode; newNode.previous = tail; newNode.next = this[head]; this[head].previous = newNode; } } }

The add() method for the circular doubly linked list accepts one argument, the data to insert into the list. If the list is empty (this[head] is null) then the new node is assigned to this[head]. The extra step to make the list circular is to ensure that both newNode.next and newNode.previous point to newNode.

If the list is not empty, then a new node is added after the current tail, which is retrieved using this[head].previous. The new node can then be added to tail.next. Remember, you are actually inserting a new node between the tail and the head of the list, so this operation looks a lot more like an insert than an append. Once complete, newNode is the list tail and therefore newNode.next must point to this[head] and this[head].previous must point to newNode.

As with a linear doubly linked list, the complexity of this add() method is O(1) because no traversal is necessary.

Retrieving data from the list

The get() method for a circular doubly linked list follows the basic algorithm from the start of this post. You must traverse the list while keeping track of how deep into the list you have gone and ensuring you don’t loop back around to the front of the list. Here is how the get() method is implemented.

class CircularDoublyLinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value and the list isn't empty if ((index > -1) && (this[head] !== null)) { let current = this[head]; let i = 0; do { if (i === index) { return current.data; } current = current.next; i++; } while ((current !== this[head]) && (i <= index)); } return undefined; } }

The get() method first checks to make sure that index is a positive value and that the list isn’t empty. If either case is true, then the method returns undefined. Remember, you must always use an if statement to check if a circular doubly linked list is empty before starting a traversal due to the use of a post-test instead of a pre-test loop.

Using the same traversal algorithm as discussed earlier, the get() method uses the i variable to track how deep into the list it has traversed. When i is equal to index, the data in that node is returned (existing the loop early). If the loop exits, either because it has reached the head of the list again or index is not found in the list, then undefined is returned.

As with a linear doubly linked list, the get() method’s complexity ranges from O(1) to O(n);

Removing data from the list

Removing data from a circular doubly linked list is basically the same as with a linear doubly linked list. The differences are:

  1. Using a post-test loop instead of a pre-test loop for the traversal (same as get())
  2. Ensuring that the circular links remain on the head and tail nodes when either is removed

Here is what the implementation of a remove() method looks like:

class CircularDoublyLinkedList { // other methods hidden for clarity remove(index) { // special cases: no nodes in the list or `index` is an invalid value if ((this[head] === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // save the current head for easier access let current = this[head]; // special case: removing the first node if (index === 0) { // if there's only one node, null out `this[head]` if (current.next === this[head]) { this[head] = null; } else { // get the last item in the list const tail = this[head].previous; /* * Set the tail to point to the second item in the list. * Then make sure that item also points back to the tail. */ tail.next = current.next; current.next.previous = tail; // now it's safe to update the head this[head] = tail.next; } // return the data at the previous head of the list return current.data; } let i = 0; do { // traverse to the next node current = current.next; // increment the count i++; } while ((current !== this[head]) && (i < index)); // the node to remove has been found if (current !== this[head]) { // skip over the node to remove current.previous.next = current.next; current.next.previous = current.previous; // return the value that was just removed from the list return current.data; } // `index` doesn't exist in the list so throw an error throw new RangeError(`Index ${index} does not exist in the list.`); } }

While there are special cases in this remove() method, almost every case requires adjusting pointers on two nodes due to the circular nature of the list. The only case where this isn’t necessary is when you are removing the only node in the list.

Removing the first node in the list (index is 0) is treated as a special case because there is no need for traversal and this[head] must be assigned a new value. The second node in the list becomes the head and it previous pointer must be adjusted accordingly.

The rest of the method follows the same algorithm as for a linear doubly linked list. As we don’t need to worry about the special this[head] pointer, the search for and removal of the node at index can proceed as if the list was linear.

You can further simply removal of nodes if you don’t mind losing track of the original head of the list. The implementation of CircularDoublyLinkedList in this post assumes you want the original head of the list to remain as such unless it is removed. However, because the list is circular, it really doesn’t matter what nodes is considered the head because you can always get to every other node as long as you reference to one node. You can arbitrarily reset this[head] to any node you want an all of the functionality will continue to work.

Creating iterators

There are two distinct use cases for iterators in a circular linked list:

  1. For use with JavaScript’s builtin iteration functionality (like for-of loops)
  2. For moving through the values of the list in a circular fashion for specific applications (like a playlist)

To address the first case, it makes sense to create a values() generator method and a Symbol.iterator method on the class as these are expected on JavaScript collections. These methods are similar to those in a doubly linked list with the usual exceptions that the loop must be flipped and the you need to check to see if you’ve reached the list head to exit the loop. Those two methods look like this:

class CircularLinkedList { // other methods hidden for clarity values() { // special case: list is empty if (this[head] !== null) { // special case: only one node if (this[head].next === this[head]) { yield this[head].data; } else { let current = this[head]; do { yield current.data; current = current.next; } while (current !== this[head]); } } } [Symbol.iterator]() { return this.values(); } }

The values() generator method has two special cases: when the list is empty, in which case it doesn’t yield anything, and when there is only one node, in which case traversal isn’t necessary and the data stored in the head is yielded. Otherwise, the do-while loop is the same as the one you’ve seen through this post.

Creating an iterator that loops around is then just a matter of modifying this algorithm so the loop never exits. Here is what that looks like:

class CircularDoublyLinkedList { // other methods hidden for clarity *circularValues() { // special case: list is empty if (this[head] !== null) { let current = this[head]; // infinite loop do { yield current.data; current = current.next; } while (true); } } }

You wouldn’t want to use the circularValues() generator method in any situation where JavaScript will drain an iterator (as in the for-of loop) because this will cause an infinite loop and crash. Instead, manually call the next() method of the iterator whenever you need another value.

For this method, it really doesn’t matter if you use a do-while loop or a while loop. I used do-while to keep it consistent with the rest of this post, but you can use any flavor of infinite loop that you want.

Using the class

Once complete, you can use the circular doubly linked list implementation like this:

const list = new CircularDoublyLinkedList(); list.add("red"); list.add("orange"); list.add("yellow"); // get the second item in the list console.log(list.get(1)); // "orange" // print out all items for (const color of list.values()) { console.log(color); } // remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the list console.log(list.get(1)); // "yellow" // convert to an array const array1 = [...list.values()]; const array2 = [...list]; // manually cycle through each item in a circular manner const iterator = list.circularValues(); let { value } = iterator.next(); doSomething(value); ({ value } = iterator.next()); doSomething(value);

The full source code is available on GitHub at my Computer Science in JavaScript project.

Conclusion

Circular doubly linked lists are setup in a similar manner as linear doubly linked lists in that each ndoe has a pointer to both the next and previous nodes in the list. The difference is that the list tail always points to the list head so you can follow next pointers and never receive null. This functionality can be used for applications such as playlists or round-robin distribution of data processing.

The implementation of doubly linked list operations differs from linear doubly linked lists in that you must use a post-test loop (do-while) to check if you’re back at the beginning of the list. For most operations, it’s important to stop when the list head has been reached again. The only exception is in creating an iterator to be called manually and which you’d prefer never ran out of items to return.

The complexity of circular doubly linked list operations is the same as with linear doubly linked list operations. Unlike the other data structures discussed in this blog post series, circular doubly linked lists can be helpful in JavaScript applications that require repeating cycling through the same data. That is one use case that isn’t covered well by JavaScript’s builtin collection types.

Categories: Tech-n-law-ogy

Computer science in JavaScript: Doubly linked lists

In my previous post, I discussed creating a singly linked list in JavaScript (if you haven’t yet read that post, I suggest doing so now). A single linked list consists of nodes that each have a single pointer to the next node in the list. Singly linked lists often require traversal of the entire list for operations, and as such, have generally poor performance. One way to improve the performance of linked lists is to add a second pointer on each node that points to the previous node in the list. A linked list whose nodes point to both the previous and next nodes is called a doubly linked list.

The design of a doubly linked list

Similar to a singly linked list, a doubly linked list is made up of a series of nodes. Each node contains some data as well as a pointer to the next node in the list and a pointer to the previous node. Here is a simple representation in JavaScript:

class DoublyLinkedListNode { constructor(data) { this.data = data; this.next = null; this.previous = null; } }

In the DoublyLinkedListNode class, the data property contains the value the linked list item should store, the next property is a pointer to the next item in the list, and the previous property is a pointer to the previous item in the list. Both the next and previous pointers start out as null because the next and previous nodes aren’t known at the time the class is instantiated. You can then create a doubly linked list using the DoublyLinkedListNode class like this:

// create the first node const head = new DoublyLinkedListNode(12); // add a second node const secondNode = new DoublyLinkedListNode(99); head.next = secondNode; secondNode.previous = head; // add a third node const thirdNode = new DoublyLinkedListNode(37); secondNode.next = thirdNode; thirdNode.previous = secondNode; const tail = thirdNode;

As with a singly linked list, the first node in a doubly linked list is called the head. The second and third nodes are assigned by using both the next and previous pointers on each node. The following image shows the resulting data structure.

You can traverse a doubly linked list in the same way as a singly linked list by following the next pointer on each node, such as:

let current = head; while (current !== null) { console.log(current.data); current = current.next; }

Doubly linked list also typically track the last node in the list, called the tail. The tail of the list is useful to track both for easier insertion of new nodes and to search from the back of the list to the front. To do so, you start at the tail and follow the previous links until there are no more nodes. The following code prints out each value in the doubly linked in reverse:

let current = tail; while (current !== null) { console.log(current.data); current = current.previous; }

This ability to go backwards and forwards through a doubly linked list provides an advantage over a singly linked list by allowing searches in both directions.

The DoublyLinkedList class

As with a singly linked list, the operations for manipulating nodes in a doubly linked list are best encapsulated in a class. Here is a simple example:

const head = Symbol("head"); const tail = Symbol("tail"); class DoublyLinkedList { constructor() { this[head] = null; this[tail] = null; } }

The DoublyLinkedList class represents a doubly linked list and will contain methods for interacting with the data it contains. There are two symbol properties, head and tail, to track the first and last nodes in the list, respectively. As with the singly linked list, the head and tail are not intended to be accessed from outside the class.

Adding new data to the list

Adding an item to a doubly linked list is very similar to adding to a singly linked list. In both data structures, you must first find the last node in the list and then add a new node after it. In a singly linked list you had to traverse the entire list to find the last node whereas in a doubly linked list the last node is tracked using the this[tail] property. Here is the add() method for the DoublyLinkedList class:

class DoublyLinkedList { constructor() { this[head] = null; this[tail] = null; } add(data) { // create the new node and place the data in it const newNode = new DoublyLinkedListNode(data); // special case: no nodes in the list yet if (this[head] === null) { this[head] = newNode; } else { // link the current tail and new tail this[tail].next = newNode; newNode.previous = this[tail]; } // reassign the tail to be the new node this[tail] = newNode; } }

The add() method for the doubly linked list accepts one argument, the data to insert into the list. If the list is empty (both this[head] and this[tail] are null) then the new node is assigned to this[head]. If the list is not empty, then a new node is added after the current this[tail] node. The last step is to set this[tail] to be newNode because in both an empty and non-empty list the new node will always be the last node.

Notice that in the case of an empty list, this[head] and this[tail] are set to the same node. That’s because the single node in a one-node list is both the first and the last node in that list. Keeping proper track of the list tail is important so the list can be traversed in reverse if necessary.

The complexity of this add() method is O(1). For both an empty and a non-empty list, the operation doesn’t require any traversal and so is much less complex than add() for the singly linked list where only the list head was tracked.

Retrieving data from the list

The get() method for a doubly linked list is exactly the same as the get() method for a singly linked list. In both cases, you must traverse the list starting from this[head] and track how many nodes have been seen to determine when the correct node is reached:

class DoublyLinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this[head]; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } } }

To reiterate from the singly linked list post, the complexity of the get() method ranges from O(1) when removing the first node (no traversal is needed) to O(n) when removing the last node (traversing the entire list is required).

Removing data from a doubly linked list

The algorithm for removing data from a doubly linked list is essentially the same as with a singly linked list: first traverse the data structure to find the node in the given position (same algorithm as get()) and then remove it from the list. The only significant differences from the algorithm used in a singly linked list are:

  1. There is no need for a previous variable to track one node back in the loop because the previous node is always available through current.previous.
  2. You need to watch for changes to the last node in the list to ensure that this[tail] remains correct.

Otherwise, the remove() method looks very similar to that of the singly linked list:

class DoublyLinkedList { // other methods hidden for clarity remove(index) { // special cases: no nodes in the list or `index` is negative if ((this[head] === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // store the data from the current head const data = this[head].data; // just replace the head with the next node in the list this[head] = this[head].next; // special case: there was only one node, so also reset `this[tail]` if (this[head] === null) { this[tail] = null; } else { this[head].previous = null; } // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this[head]; // used to track how deep into the list you are let i = 0; // same loop as in `get()` while ((current !== null) && (i < index)) { // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove current.previous.next = current.next; // special case: this is the last node so reset `this[tail]`. if (this[tail] === current) { this[tail] = current.previous; } else { current.next.previous = current.previous; } // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); } }

When index is 0, meaning the first node is being removed, this[head] is set to this[head].next, the same as with a singly linked list. The difference comes after that point when you need to update other pointers. If there was only one node in the list, then you need to set this[tail] to null to effectively remove that one node; if there was more than one node, you need to set this[head].previous to null. Remember that the new head was previously the second node in the list and so its previous link was pointing to the node that was just removed.

After the loop, you need to ensure that both the next pointer of the node before the removed node and the previous pointer of the node after the removed node. Of course, if the node to remove is the last node then you need to update the this[tail] pointer.

Creating a reverse iterator

You can make a doubly linked list iterable in JavaScript using the same values() and Symbol.iterator methods from the singly linked list. In a doubly linked list, however, you have the opportunity to create a reverse iterator that produces the data starting from the tail and working its way towards the head. Here is what a reverse() generator method looks like:

class DoublyLinkedList { // other methods hidden for clarity *reverse(){ // start by looking at the tail let current = this[tail]; // follow the previous links to the head while (current !== null) { yield current.data; current = current.previous; } } }

The reverse() generator method follows the same algorithm as the values() generator method in the singly linked list with the exception that current starts equal to this[tail] and the current.previous is followed until the there are no more nodes. Creating a reverse iterator is helpful for discovering bugs in the implementation as well as avoiding rearranging nodes just to access the data in a different order.

Other methods

Most other methods that don’t involve addition or removal of nodes follow the same algorithms as those in a singly linked list.

Using the class

Once complete, you can use the linked list implementation like this:

const list = new DoublyLinkedList(); list.add("red"); list.add("orange"); list.add("yellow"); // get the second item in the list console.log(list.get(1)); // "orange" // print out all items in reverse for (const color of list.reverse()) { console.log(color); } // remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the list console.log(list.get(1)); // "yellow" // convert to an array const array1 = [...list.values()]; const array2 = [...list]; const array3 = [...list.reverse()];

The full source code is available on GitHub at my Computer Science in JavaScript project.

Conclusion

Doubly linked lists are similar to singly linked lists in that each node has a next pointer to the next node in the list. Each node also has a previous pointer to the previous node in the list, allowing you to move both backwards and forwards in the list easily. Doubly linked lists typically track both the first and last node in the list, and that makes adding a node into the list a O(1) operation instead of O(n) in a singly linked list.

However, the complexity of other doubly linked list operations is the same as with a singly linked list because you always end up traversing most of the list. As such, doubly linked lists don’t offer any real advantage over the built-in JavaScript Array class for storing a collection of unrelated data (though related data, such as sibling DOM nodes in the browser) might be useful to represent in some kind of linked list.

Categories: Tech-n-law-ogy

Legaltech 2019 – I Finally Made It

Legaltech 2019

It is, in fact, a little embarrassing. I have been writing about legal technology issues for probably close to a decade. However, I have never been able to get myself to Legaltech. Legaltech has been going on far longer than I and perhaps other readers may suspect – it all started in 1982 when Janet Felleman joined forces with Price Waterhouse to teach lawyers how to use tech in their law practice. Fast forward through a couple of handoffs and mergers, and it is now conducted by ALM. It also is part of a larger gathering called Legalweek, during which legal professionals discuss more than just shiny cool technology. But that is not the focus of this blog. 

I didn’t quite know what to expect, but thought I would likely see lots of vendors with various offerings with some technology angle. I also thought I would see a few sessions on tech-related topics that might arise in the course of one’s practice. I was right on both of those accounts. I also anticipated more of a firm focus, rather than in house legal department focus. On that latter account, I was a bit off the mark. The conference started with a State of the Industry address offering a more global view of the legal industry, addressing firms, in house legal departments and the newer entrant in the space – Alternative Legal Service Providers. ALM analysts touched on current events in the legal industry to the present, as well as trends for the future. This included a striation of firms between “bet the company” top tier firms and ALS providers who can offer innovative and efficient solutions to higher frequency, lower severity or repetitive matters. Coupled with concepts of increased in-sourcing by corporate clients and their in-house legal departments, it is clear to see that the practice of law is changing dramatically and that trajectory isn’t going to flatten any time soon.

Alberto Gonzales

Another nice surprise was the keynote from former U.S. Attorney Generals Alberto Gonzales and Loretta Lynch. While it made an appearance in the discussions, the former A.G.’s did not focus on technology. I found the keynote very timely given our current climate and a nice “forest for the trees” view of the larger geopolitical legal landscape. And, as one might expect, cybersecurity is a top level concern of our government lawyers.

Loretta Lynch

I still saw tech and lots of it. I visited almost 20 different vendors, with a focus on artificial intelligence, consulting and analytics solutions. I also got a chance to catch up with Nicole Black of MyCase and Bob Ambrogi of Lawsites, as well as Doug Kaminski of CobrATX. I was impressed with Fastcase’s Docket Alarm – an award winner at the show – that offers full text docket search and alerts, as well as analytics, for federal and some state courts. I also was intrigued by audio analytics tools. These were primarily advertised in the context of e-discovery, but I can see the potential behavioral analysis that expand beyond discovery and into predictive customer analytics. There were a few vendors offering this and I am interested to see what the future might hold there.

I attended a few sessions, but my favorite was an ILTA educational track session on how to innovate and get client buy-in on a budget, which is a particular focus of mine at present. I really enjoyed hearing how Andrew Price, COO of the Australian firm Barry Nilsson, approached innovation projects, as well as the more general tips offered by Gina Buser of Traveling Coaches and TJ Johnson of Olenick. Definitely some good information that I anticipate may help me in my in-house setting.

While it was a VERY long day, I really enjoyed my experience. Anecdotally, I was told that vendor exhibits seemed smaller and more reserved than in prior years. However, without that historical perspective, I found plenty to keep me occupied for a full day and could have easily returned for some of the interesting sessions offered on days two and three. I am hoping to return next year with the benefit of prior experience. In the meantime, I will continue to ask myself the question “What took me so long?”

Categories: Tech-n-law-ogy

The Best Cybersecurity and Computer Security Services for Your Company

If you have a company or a business, one of the most important things that you have is your data. Your data is one of the most valuable assets that you have as a company. It holds all the information about your key stakeholders, your customers, your sales, your product, as well as other confidential information. You do not want all those things to fall into the wrong hands. That is why you need data protection.

One of the things that you should get is cybersecurity Cincinnati to protect your data. You need to hire cybersecurity and computer security to protect your data so that it doesn't leak out of your company. Not only do you need to find a company for hire, but you also need to hire the best one. In this article, we are going to talk about several considerations that you need to keep in mind when you want to hire cybersecurity and computer security services for your company. Here are a few things for you to consider:

Why You Need It

Other than the reasons mentioned above, you need to always keep in mind that your data is precious. You need to protect it like you would protect the crown jewels. If you have cybersecurity, you won't be distraught by worrying about your vital information being hacked. You will feel secure that there is a safeguard against not just hackers, but also malware and viruses. You sleep tightly knowing that you have ensured security from not only external threats but internal threats as well.

How to Look for the Best

If you want to look for the best, then the first thing that you need to do is go online. Search for companies that can provide you with these services in your area. Take note of all the potential ones that you have found. Visit all their websites and browse around. Make sure that you check everything. Check their services, their reviews, and their prices. You can also ask for recommendations and references from colleagues that you trust.

What to Look For

When it comes to choosing the best, you want to look for a company that is experienced in this field. You want one that has been around for quite some time and knows what they are doing. You also should be looking for a reputable company with an excellent reputation and trusted credentials. Other than that, you also need to look at the services that they offer. Make sure that the customer service is excellent. You should also read their reviews.…

Categories: Tech-n-law-ogy

Why I've stopped exporting defaults from my JavaScript modules

Last week, I tweeted something that got quite a few surprising responses:

In 2019, one of the things I’m going to do is stop exporting things as default from my CommonJS/ES6 modules.

Importing a default export has grown to feel like a guessing game where I have a 50/50 chance of being wrong each time. Is it a class? Is it a function?

— Nicholas C. Zakas (@slicknet) January 12, 2019

I tweeted this after realizing that a lot of problems I had with JavaScript modules could be traced back to fights with default exports. It didn’t matter if I was using JavaScript modules (or ECMAScript modules, as many prefer to call them) or CommonJS, I was still stumbling over importing from modules with default exports. I got a variety of responses to the tweet, many of which questioned how I could come to this decision. This post is my attempt to clarify my thinking.

A few clarifications

As is the case with all tweets, my tweet was meant as a snapshot into an opinion I had rather than a normative reference for my entire opinion. To clarify a few points people seem confused by on Twitter:

  • The use case of knowing whether an export is a function or a class was an example of the type of problems I’ve encountered. It is not the only problem I’ve found named exports solve for me.
  • The problems I’ve encountered don’t just happen with files in my own projects, they also happen with importing library and utility modules that I don’t own. That means naming conventions for filenames don’t solve all of the problems.
  • I’m not saying that everyone should abandon default exports. I’m saying that in modules I’m writing, I will choose not to use default exports. You may feel differently, and that’s fine.

Hopefully those clarifications setup enough context to avoid confusion throughout the rest of this post.

Default exports: A primer

To the best of my knowledge, default exports from modules were first popularized in CommonJS, where a module can export a default value like this:

class LinkedList {} module.exports = LinkedList;

This code exports the LinkedList class but does not specify the name to be used by consumers of the module. Assuming the filename is linked-list.js, you can import that default in another CommonJS module like this:

const LinkedList = require("./linked-list");

The require() function is returning a value that I just happened to name LinkedList to match what is in linked-list.js, but I also could have chosen to name it foo or Mountain or any random identifier.

The popularity of default module exports in CommonJS meant that JavaScript modules were designed to support this pattern:

ES6 favors the single/default export style, and gives the sweetest syntax to importing the default.

— David Herman June 19, 2014

So in JavaScript modules, you can export a default like this:

export default class LinkedList {}

And then you can import like this:

import LinkedList from "./linked-list.js";

Once again, LinkedList is this context is an arbitrary (if not well-reasoned) choice and could just as well be Dog or symphony.

The alternative: named exports

Both CommonJS and JavaScript modules support named exports in addition to default exports. Named exports allow for the name of a function, class, or variable to be transferred into the consuming file.

In CommonJS, you create a named export by attaching a name to the exports object, such as:

exports.LinkedList = class LinkedList {};

You can then import in another file like this:

const LinkedList = require("./linked-list").LinkedList;

Once again, the name I’ve used with const can be anything I want, but I’ve chosen to match it to the exported name LinkedList.

In JavaScript modules, a named export looks like this:

export class LinkedList {}

And you can import like this:

import { LinkedList } from "./linked-list.js";

In this code, LinkedList cannot be a randomly assigned identifier and must match an named export called LinkedList. That’s the only significant difference from CommonJS for the goals of this post.

So the capabilities of both module types support both default and named exports.

Personal preferences

Before going further, it’s helpful for you to know some of my own personal preferences when it comes to writing code. These are general principles I apply to all code that I write, regardless of the programming language I use:

  1. Explicit over implicit. I don’t like having code with secrets. What something does, what something should be called, etc., should always be made explicit whenever possible.
  2. Names should be consistent throughout all files. If something is an Apple in one file, I shouldn’t call it Orange in another file. An Apple should always be an Apple.
  3. Throw errors early and often. If it’s possible for something to be missing then it’s best to check as early as possible and, in the best case, throw an error that alerts me to the problem. I don’t want to wait until the code has finished executing to discover that it didn’t work correctly and then hunt for the problem.
  4. Fewer decisions mean faster development. A lot of the preferences I have are for eliminating decisions during coding. Every decision you make slows you down, which is why things like coding conventions lead to faster development. I want to decide things up front and then just go.
  5. Side trips slow down development. Whenever you have to stop and look something up in the middle of coding, I call that a side trip. Side trips are sometimes necessary but there are a lot of unnecessary side trips that can slow things down. I try to write code that eliminates the need for side trips.
  6. Cognitive overhead slows down development. Put simply: the more detail you need to remember to be productive when writing code, the slower your development will be.

The focus on speed of development is a practical one for me. As I’ve struggled with my health for years, the amount of energy I’ve had to code continued to decrease. Anything I could do to reduce the amount of time spent coding while still accomplishing my task was key.

The problems I’ve run into

With all of this in mind, here are the top problems I’ve run into using default exports and why I believe that named exports are a better choice in most situations.

What is that thing?

As I mentioned in my original tweet, I find it difficult to figure out what I’m importing when a module only has a default import. If you’re using a module or file you’re unfamiliar with, it can be difficult to figure out what is returned, for example:

const list = require("./list");

In this context, what would you expect list to be? It’s unlikely to be a primitive value, but it could logically be a function, class, or other type of object. How will I know for sure? I need a side trip. In this case, a side trip might be any of:

  • If I own list.js, then I may open the file and look for the export.
  • If I don’t own list.js, then I may open up some documentation.

In either case, this now becomes an extra bit of information you need in your brain to avoid a second side trip penalty when you need to import from list.js again. If you are importing a lot of defaults from modules then either your cognitive overhead is increasing or the number of side trips is increasing. Both are suboptimal and can be frustrating.

Some will say that IDEs are the answer to this problem, that the IDEs should be smart enough to figure out what is being imported and tell you. While I’m all for smarter IDEs to help developers, I believe requiring IDEs to effectively use a language feature is problematic.

Name matching problems

Named exports require consuming modules to at least specify the name of the thing they are importing from a module. The benefit is that I can easily search for everywhere that LinkedList is used in a code base and know that it all refers to the same LinkedList. As default exports are not prescriptive of the names used to import them, that means naming imports becomes more cognitive overhead for each developer. You need to determine the correct naming convention, and as extra overhead, you need to make sure every developer working in the application will use the same name for the same thing. (You can, of course, allow each developer to use different names for the same thing, but that introduces more cognitive overhead for the team.)

Importing a named export means at least referencing the canonical name of a thing everywhere that it’s used. Even if you choose to rename an import, the decision is made explicit, and cannot be done without first referencing the canonical name in some way. In CommonJS:

const MyList = require("./list").LinkedList;

In JavaScript modules:

import { LinkedList as MyList } from "./list.js";

In both module formats, you’ve made an explicit statement that LinkedList is now going to be referred to as MyList.

When naming is consistent across a codebase, you’re able to easily do things like:

  1. Search the codebase to find usage information.
  2. Refactor the name of something across the entire codebase.

Is it possible to do this when using default exports and ad-hoc naming of things? My guess is yes, but I’d also guess that it would be a lot more complicated and error-prone.

Importing the wrong thing

Named exports in JavaScript modules have a particular advantage over default exports in that an error is thrown when attempting to import something that doesn’t exist in the module. Consider this code:

import { LinkedList } from "./list.js";

If LinkedList doesn’t exist in list.js, then an error is thrown. Further, tools such as IDEs and ESLint1 are easily able to detect a missing reference before the code is executed.

Worse tooling support

Speaking of IDEs, WebStorm is able to help write import statements for you.2 When you have finished typing an identifier that isn’t defined in the file, WebStorm will search the modules in your project to determine if the identifier is a named export in another file. At that point, it can do any of the following:

  1. Underline the identifier that is missing its definition and show you the import statement that would fix it.
  2. Automatically add the correct import statement (if you have enable auto import) can now automatically add an import statement based on an identifier that you type. In fact, WebStorm is able to help you a great deal when using named imports:

There is a plugin for Visual Studio Code3 that provides similar functionality. This type of functionality isn’t possible when using default exports because there is no canonical name for things you want to import.

Conclusion

I’ve had several productivity problems importing default exports in my projects. While none of the problems are necessarily impossible to overcome, using named imports and exports seems to better fit my preferences when coding. Making things explicit and leaning heavily on tooling makes me a productive coder, and insofar as named exports help me do that, I will likely favor them for the foreseeable future. Of course, I have no control over how third-party modules I use export their functionality, but I definitely have a choice over how my own modules export things and will choose named exports.

As earlier, I remind you that this is my opinion and you may not find my reasoning to be persuasive. This post was not meant to persuade anyone to stop using default exports, but rather, to better explain to those that inquired why I, personally, will stop exporting defaults from the modules I write.

References
  1. esling-plugin-import import/named rule 

  2. WebStorm: Auto Import in JavaScript 

  3. Visual Studio Extension: Auto Import 

Categories: Tech-n-law-ogy

Reasons Why Mini Cameras Are Advantageous

The demands of mini spy cameras have increased over the past five years, proving that the practice of installing a hidden surveillance camera has been a widespread phenomenon. While it is true that years ago, the devices were only prevalent among office workers and in many public domains, the items now are the subject of domestic use. In short, installing the device at home for safety reasons is now becoming more and more common. Technology experts often refer to this phenomenon and state that this practice is likely to continue for the coming years. Of course, massive changes and additional advanced features will be part of its developments.

The above explanation relates to how people can benefit from the device as they are on a constant lookout for more features. Indeed, the camera does not only serve as your second pair of eyes while you are not around, but it also helps to perform multiple tasks at the same time, such as scanning faces, audio recording, and taking pictures. Thus, this article tries to highlight the benefits that the device has for your property.



The Small Size

The size of the device will come in handy whenever you need to install a hidden surveillance camera to keep an eye of your target without telling them about the presence of the device. It is especially helpful for office use, especially when you need to assess the employees’ performance at work. The size is especially useful for the task since you can put the device in a completely hidden area. Apart from the office use, nanny cams are also another example of the possible use. Although some sites categorize the nanny cam as an independent subject, the application still holds the same concept with the use of mini cameras.

It Is Affordable

Although the use of the device was prevalent only for those running a company, which means the item was sold at high prices, the high demands have caused the prices to drop. As a result, the cameras now are becoming more and more affordable, and it encourages more people to use the item. Another great thing about this item is that it often comes with more new features, making the users believe that they pay less than what they get.

The Features

The device has been going through massive developments for the last five years, and it leads to more new features that the users can benefit from. These features include built-in audio recorders, night vision, durability, and compatibility with mobile applications. All these new features should be present in essential best mini camera guide.…

Categories: Tech-n-law-ogy

Computer science in JavaScript 2019: Linked list

Back in 2009, I challenged myself to write one blog post per week for the entire year. I had read that the best way to gain more traffic to a blog was to post consistently. One post per week seemed like a realistic goal due to all the article ideas I had but it turned out I was well short of 52 ideas. I dug through some half-written chapters what would eventually become Professional JavaScript and found a lot of material on classic computer science topics, including data structures and algorithms. I took that material and turned it into several posts in 2009 and (and a few in 2012), and got a lot of positive feedback on them.

Now, at the ten year anniversary of those posts, I’ve decided to update, republish, and expand on them using JavaScript in 2019. It’s been interesting to see what has changed and what hasn’t, and I hope you enjoy them.

What is a linked list?

A linked list is a data structure that stores multiple values in a linear fashion. Each value in a linked list is contained in its own node, an object that contains the data along with a link to the next node in the list. The link is a pointer to another node object or null if there is no next node. If each node has just one pointer to another node (most frequently called next) then the list is considered a singly linked list (or just linked list) whereas if each node has two links (usually previous and next) then it is considered a doubly linked list. In this post, I am focusing on singly linked lists.

Why use a linked list?

The primary benefit of linked lists is that they can contain an arbitrary number of values while using only the amount of memory necessary for those values. Preserving memory was very important on older computers where memory was scarce. At that time, a built-in array in C required you to specify how many items the array could contain and the program would reserve that amount of memory. Reserving that memory meant it could not be used for the rest of the program or any other programs running at the same time, even if the memory was never filled. One memory-scarce machines, you could easily run out of available memory using arrays. Linked lists were created to work around this problem.

Though originally intended for better memory management, linked lists also became popular when developers didn’t know how many items an array would ultimately contain. It was much easier to use a linked list and add values as necessary than it was to accurately guess the maximum number of values an array might contain. As such, linked lists are often used as the foundation for built-in data structures in various programming languages.

The built-in JavaScript Array type is not implemented as a linked list, though its size is dynamic and is always the best option to start with. You might go your entire career without needing to use a linked list in JavaScript but linked lists are still a good way to learn about creating your own data structures.

The design of a linked list

The most important part of a linked list is its node structure. Each node must contain some data and a pointer to the next node in the list. Here is a simple representation in JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; } }

In the LinkedListNode class, the data property contains the value the linked list item should store and the next property is a pointer to the next item in the list. The next property starts out as null because you don’t yet know the next node. You can then create a linked list using the LinkedListNode class like this:

// create the first node const head = new LinkedListNode(12); // add a second node head.next = new LinkedListNode(99); // add a third node head.next.next = new LinkedListNode(37);

The first node in a linked list is typically called the head, so the head identifier in this example represents the first node. The second node is created an assigned to head.next to create a list with two items. A third node is added by assigning it to head.next.next, which is the next pointer of the second node in the list. The next pointer of the third node in the list remains null. The following image shows the resulting data structure.

The structure of a linked list allows you to traverse all of the data by following the next pointer on each node. Here is a simple example of how to traverse a linked list and print each value out to the console:

let current = head; while (current !== null) { console.log(current.data); current = current.next; }

This code uses the variable current as the pointer that moves through the linked list. The current variable is initialized to the head of the list and the while loop continues until current is null. Inside of the loop, the value stored on the current node is printed and then the next pointer is followed to the next node.

Most linked list operations use this traversal algorithm or something similar, so understanding this algorithm is important to understanding linked lists in general.

The LinkedList class

If you were writing a linked list in C, you might stop at this point and consider your task complete (although you would use a struct instead of a class to represent each node). However, in object-oriented languages like JavaScript, it’s more customary to create a class to encapsulate this functionality. Here is a simple example:

const head = Symbol("head"); class LinkedList { constructor() { this[head] = null; } }

The LinkedList class represents a linked list and will contain methods for interacting with the data it contains. The only property is a symbol property called head that will contain a pointer to the first node in the list. A symbol property is used instead of a string property to make it clear that this property is not intended to be modified outside of the class.

Adding new data to the list

Adding an item into a linked list requires walking the structure to find the correct location, creating a new node, and inserting it in place. The one special case is when the list is empty, in which case you simply create a new node and assign it to head:

const head = Symbol("head"); class LinkedList { constructor() { this[head] = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this[head] === null) { // just set the head to the new node this[head] = newNode; } else { // start out by looking at the first node let current = this[head]; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } } }

The add() method accepts a single argument, any piece of data, and adds it to the end of the list. If the list is empty (this[head] is null) then you assign this[head] equal to the new node. If the list is not empty, then you need to traverse the already-existing list to find the last node. The traversal happens in a while loop that start at this[head] and follows the next links of each node until the last node is found. The last node has a next property equal to null, so it’s important to stop traversal at that point rather than when current is null (as in the previous section). You can then assign the new node to that next property to add the data into the list.

Traditional algorithms use two pointers, a current that points to the item being inspected and a previous that points to the node before current. When current is null, that means previous is pointing to the last item in the list. I don’t find that approach very logical when you can just check the value of current.next and exit the loop at that point.

The complexity of the add() method is O(n) because you must traverse the entire list to find the location to insert a new node. You can reduce this complexity to O(1) by tracking the end of the list (usually called the tail) in addition to the head, allowing you to immediately insert a new node in the correct position.

Retrieving data from the list

Linked lists don’t allow random access to its contents, but you can still retrieve data in any given position by traversing the list and returning the data. To do so, you’ll add a get() method that accepts a zero-based index of the data to retrieve, like this:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this[head]; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } } }

The get() method first checks to make sure that index is a positive value, otherwise it returns undefined. The i variable is used to keep track of how deep the traversal has gone into the list. The loop itself is the same basic traversal you saw earlier with the added condition that the loop should exit when i is equal to index. That means there are two conditions under which the loop can exit:

  1. current is null, which means the list is shorter than index.
  2. i is equal to index, which means current is the node in the index position.

If current is null then undefined is returned and otherwise current.data is returned. This check ensures that get() will never throw an error for an index that isn’t found in the list (although you could decide to throw an error instead of returning undefined).

The complexity of the get() method ranges from O(1) when removing the first node (no traversal is needed) to O(n) when removing the last node (traversing the entire list is required). It’s difficult to reduce complexity because a search is always required to identify the correct value to return.

Removing data from a linked list

Removing data from a linked list is a little bit tricky because you need to ensure that all next pointers remain valid after a node is removed. For instance, if you want to remove the second node in a three-node list, you’ll need to ensure that the first node’s next property now points to the third node instead of the second. Skipping over the second node in this way effectively removes it from the list.

The remove operation is actually two operations:

  1. Find the specified index (the same algorithm as in get())
  2. Remove the node at that index

Finding the specified index is the same as in the get() method, but in this loop you also need to track the node that comes before current because you’ll need to modify the next pointer of the previous node.

There are also four special cases to consider:

  1. The list is empty (no traversal is possible)
  2. The index is less than zero
  3. The index is greater than the number of items in the list
  4. The index is zero (removing the head)

In the first three cases, the removal operation cannot be completed, and so it makes sense to throw an error; the fourth special case requires rewriting the this[head] property. Here is what the implementation of a remove() method looks like:

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this[head] === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this[head].data; // just replace the head with the next node in the list this[head] = this[head].next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this[head]; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); } }

The remove() method first checks for two special cases, an empty list (this[head] is null) and an index that is less than zero. An error is thrown in both cases.

The next special case is when index is 0, meaning that you are removing the list head. The new list head should be the second node in the list, so you can set this[head] equal to this[head].next. It doesn’t matter if there’s only one node in the list because this[head] would end up equal to null, which means the list is empty after the removal. The only catch is to store the data from the original head in a local variable, data, so that it can be returned.

With three of the four special cases taken care of, you can now proceed with a traversal similar to that found in the get() method. As mentioned earlier, this loop is slightly different in that the previous variable is used to keep track of the node that appears just before current, as that information is necessary to propely remove a node. Similar to get(), when the loop exits current may be null, indicating that the index wasn’t found. If that happens then an error is thrown, otherwise, previous.next is set to current.next, effectively removing current from the list. The data stored on current is returned as the last step.

The complexity of the remove() method is the same as get() and ranges from O(1) when removing the first node to O(n) when removing the last node.

Making the list iterable

In order to be used with the JavaScript for-of loop and array destructuring, collections of data must be iterables. The built-in JavaScript collections such as Array and Set are iterable by default, and you can make your own classes iterable by specifying a Symbol.iterator generator method on the class. I prefer to first implement a values() generator method (to match the method found on built-in collection classes) and then have Symbol.iterator call values() directly.

The values() method need only do a basic traversal of the list and yield the data that each node contains:

class LinkedList { // other methods hidden for clarity *values(){ let current = this[head]; while (current !== null) { yield current.data; current = current.next; } } [Symbol.iterator]() { return this.values(); } }

The values() method is marked with an asterisk (*) to indicate that it’s a generator method. The method traverses the list, using yield to return each piece of data it encounters. (Note that the Symbol.iterator method isn’t marked as a generator because it is returning an iterator from the values() generator method.)

Using the class

Once complete, you can use the linked list implementation like this:

const list = new LinkedList(); list.add("red"); list.add("orange"); list.add("yellow"); // get the second item in the list console.log(list.get(1)); // "orange" // print out all items for (const color of list) { console.log(color); } // remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the list console.log(list.get(1)); // "yellow" // convert to an array const array1 = [...list.values()]; const array2 = [...list];

This basic implementation of a linked list can be rounded out with a size property to count the number of nodes in the list, and other familiar methods such as indexOf(). The full source code is available on GitHub at my Computer Science in JavaScript project.

Conclusion

Linked lists aren’t something you’re likely to use every day, but they are a foundational data structure in computer science. The concept of using nodes that point to one another is used in many other data structures are built into many higher-level programming languages. A good understanding of how linked lists work is important for a good overall understanding of how to create and use other data structures.

For JavaScript programming, you are almost always better off using the built-in collection classes such as Array rather than creating your own. The built-in collection classes have already been optimized for production use and are well-supported across execution environments.

Categories: Tech-n-law-ogy

Buying the Best Drone in the Market

Among the gadgets that have improved photo taking experience according to ddcountermeasures.com are drones. People have always looked for ways to capture not only better pictures but have views from different angles. With much success in improving camera quality, the remaining part was the angles. And now with drones, this problem has been solved. Currently, you can buy an excellent drone that is mounted with the best camera, and without a doubt, your photo taking experience will never be the same again. However, you need to be keen so that you buy the best drone. Online stores and vendors are selling a variety of drones. However, you need to be wise and differentiate them before making a purchase. Written here are ideas to help you select the best.

Google

The first thing to do if you do not know much about drones is to research. And there is no place you can find information like online. This is the information generation as you may already know, and the Internet is what drives it. While online you will be able to see the different drones and learn about each of their pros and cons. What makes Google even better is the fact that you will be able to read reviews posted by different buyers before making your choice.

Brand

As you gather information online about the various drones, you should remember to note down the different brands. Understand that renowned brands make better products, and you can know a quality brand by reading reviews and seeing what people are saying about their products. As usual, a good brand will always have excellent reviews. Also as you check out the different brands, you should remember to note the specific models.

Flight Time

If you are keen on your search for a drone, you will realize that these gadgets come with varying battery life. Meaning that some can fly and take photos for longer while others take them just for few minutes. If your passion is to take pictures and record videos, you may have to choose a gadget that has a longer battery life. However, you can also inquire if the drone you are about to buy has extra batteries that you can use when the primary one runs out.

Cost

The last but also essential point you must consider is the price. Usually, drones are not expensive. However, if you want an excellent drone with excellent features, then you may have to spend a little extra.…

Categories: Tech-n-law-ogy
Subscribe to www.dgbutterworth.com aggregator - Tech-n-law-ogy