A trie is a tree-like data structure in which every node stores a character. It can store multiple words. After building a trie, strings or substrings can be retrieved by traversing down a path (a branch) of the trie. Insert a word in a trie, search a word, or delete a word by key all takes O(n) time, at the expense of storage. This post is trie implementation using a linked list.

trie diagram

Why is a singly linked list used in a trie node?

In a trie, each trie node might have multiple branches. So a data structure is used to find next nodes in branches. This data structure can be an array, a linked list, or a hash map. Each implementation has its pros and cons. In array implementation, the next character in the node will be used as the index to find the child nodes. However, most cells in the array are empty which is not space efficient. A linked list overcomes this problem by creating nodes only for the next characters in branches. But this require time to find the right child by search each node in the list. So this implementation uses time to trade space.

you are here

Part 1 – Trie implementation using array
Part 2 – Trie implementation using linked list
Part 3 – Trie implementation using hash map

Table of Content


Define classes in trie implementation

Like building a tree, you need to define a TrieNode class before a Trie class. The trie node class has tree variables: data stores a character, children is a data structure that points to the children nodes; isEnd is to mark whether this is the last node of the branch. In Trie class, there is one variable root. The operation of insertion, search or deletion always starts from root.

Java

Javascript

Python


Insert in trie implementation

To insert a word, first check whether the word is in the trie so that you don’t insert a duplicate word. Then you loop through each character in the word. A pointer node starts from root. If the next character is not in the node‘s children, a child node is created. Then the node moves to the child node. When the node is at the last character of the word, you mark the node‘s isEnd to be true.

Java

Javascript

Python

Doodle

trie insert array


Delete

To delete a word from a trie, first check whether the word exists in the trie. If not, the method can return. Otherwise, continue.  The same as insertion, loop through each character in the word. A pointer node starts from root. If the next character is not in the node‘s children, the method returns directly. Otherwise, the node moves to the child node. When the node is at the last character of the word, mark the node‘s isEnd to be false.

Java

Javascript

Python

To search a word in a trie, loop through each character in the word. A pointer node starts from root. If the next character is not in the node‘s children, the method returns false. Otherwise, the node moves to the child node. When the node is at the last character of the word, return the node‘s isEnd value, which can be true or false (deleted).

Java

Javascript

Python


Print

To print all words in a trie, recursion is used to traverse all nodes in the trie. This is similar to preorder (DFS, depth first search) of a tree. When visiting the node, the method concatenates characters from previously visited nodes with the character of the current node. When the node‘s isEnd is true, the recursion reaches the last character of the word, and add the word to the result list.

Java

Javascript

Python


Free download

Download trie implementation using linked list in Java, JavaScript and Python
Data structures introduction PDF