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

A Bot-Champion for Financially-Inclined Women!

Kudos to the Financial Times, that bastion of male writers covering male-dominated endeavors and industries! It recognized that there are women who might be interested in their articles! Also, it noted that not enough women experts were being leveraged in their articles! Finally, it recognized research that suggests that women might be put off by articles that quote heavily or exclusively from men! So, FT sourced the effort to correct this situation to a Bot – call it a “FemBot” if you will (my name, not theirs). This bot scans through the articles during the editing process to determine whether the sources named in the article are male or female. Editors are then alerted that they are falling short on including women in their pieces. Later versions might actually alert writers to their overly male tone as they type their articles.

FT isn’t stopping there. It is also examining the images it uses, and intends to press for more pictures of women. Because women are more likely to click through on pictures of women, then those only containing men. The Opinion Desk at the FT is also tracking behaviors, to note gender, ethnicity and geographical location – with the goal of supporting more female and minority voices in the publication.

The concept of bias baked into Artificial Intelligence systems from developers and data sets is an emerging issue and well-identified risk. However, FT appears to be embracing the bias in an effort to counteract it. Well done, FT!

 

Categories: Tech-n-law-ogy

Setting Up a Good Business Website

Operating a business can be difficult for many. You might face with several challenges that will at times force you to quit. This should be the last option because there are several measures you can take that will give you an edge over your competitors. You need to adapt to the changing trends in technology and implement them in your business.

One good thing you should do is come up with a good business website. It is a perfect way of marketing your business. A good business website will help attract more customers. Many will be eager to know the kind of products you are selling or services offered. Having one will also help build the reputation of your business. Most people will relate to the type of products or services you are offering.

The other thing you can implement is search engine optimization also known as SEO. It involves the use of several strategies that help get your site ranked top in most search engines. Your business website will top the list in search engines like Google, Yahoo, and Bing when you implement this strategy. It helps increase leads to your site to a certain extent. There are several things you should do to set up a website that is good for your business. They include:

Finding a Web Designer

You should look for a good web designer who will come up with a good website for your business. One thing you should look out for when hiring one is their level of expertise. You can judge one by having a look at some of their previous projects. Go for one with designs that match your preference.

Company Logo

Your business or company logo is another essential element for your website. You need to come up with one that is unique and stands out from the rest. Your designer can use different available software to come up with the best. It should be attractive and portray all the good qualities of your company.

Easy to Maneuver

Your designer should build a website that is easy to maneuver. People from various classes or walks of life will be visiting your site to have a look at the products or services you have to offer. Let them have an easy time going through it. Your web designer should also work on its appearance. One must ensure that it is attractive for everyone visiting the site.

Categories: Tech-n-law-ogy

Booking a Taxi Online

There are various means of transportation in most big cities. They have helped simplify movements from one place to another. Some of the conventional transport means include buses, bikes, trains, and taxis. Taxis remain a popular means of transport in most cities, and they are preferred by many.

One reason many prefer them is because of the level of comfort they get to enjoy when using them. Unlike other public transport means, you get to enjoy your own space in taxis since they are not crowded. Most of them are usually a personal vehicle. Taxis are also fast since there is no need to wait for one to fill up which is the case when using public means of transportation. Accessing them is also much more comfortable.

The improvements in technology have seen most taxi companies employ the use of taxi apps to simplify booking. Before this, one would have to call or look for taxis physically. Taxi apps are quite easy to use because you can trace the taxis that are nearby using their booking app.

When you trace one, you can book immediately by keying in your destination. Your driver will be there in a minute to pick you for your trip. Most apps will indicate the charges for your trip. Online taxi booking apps have helped make our lives easier. There are several benefits you get to enjoy when you use them. They include:

Saves You Time

You get to save a lot of time when you use different online taxi booking apps. Waiting for a taxi by the roadside can use up much of your time. It is also the same when it comes to walking to a specific spot to get a taxi. With the online taxi booking apps, you will have one coming to your current location within a short time.

It is Cheap

Online taxi companies are very cheap compared to the regular ones. Most of them usually charge per kilometer which is different in the regular taxis that place a random charge without considering the distance you have covered. You can opt for online taxi companies to save more money.

Easy to Use

The online taxi application has been designed in a manner which is easy to use for anyone. All you need to do is download the app and key in the required details. The booking process is easy because you will be required to have a stable internet connection to trace available taxis before booking one. Your driver will be available minutes after booking your trip.

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