Linear Data Structures

Various applications, such as Facebook, Twitter, and Google, use lists and linear data structures. As we have discussed previously, data structures allow us to organize vast swathes of data in a sequential and organized manner, thereby reducing time and effort in working with such data. Lists, stacks, sets, and tuples are some of the commonly used linear data structures.

In this chapter, we will discuss these data structures by giving examples of various procedures involving them. We will discuss the various operations related to these data structures, such as insertion, deletion, updating, traversing (of lists), reversing, and merging with various code samples.

We will cover the following linear data structures in this chapter:

• Lists
• Sets
• Tuples
• Stacks

Technical requirements

Install Go version 1.10 at https://golang.org/doc/install, depending on your operating system.

The code files for this chapter can be found at the following GitHub URL: https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/Chapter03.

Lists

A list is a collection of ordered elements that are used to store list of items. Unlike array lists, these can expand and shrink dynamically.

Lists also be used as a base for other data structures, such as stack and queue. Lists can be used to store lists of users, car parts, ingredients, to-do items, and various other such elements. Lists are the most commonly used linear data structures. These were introduced in the lisp programming language. In this chapter, linked list and doubly linked list are the lists we will cover in the Go language.

Let's discuss the operations related to add, update, remove, and lookup on linked list and doubly linked list in the following section.

LinkedList

LinkedList is a sequence...

Sets

A Set is a linear data structure that has a collection of values that are not repeated. A set can store unique values without any particular order. In the real world, sets can be used to collect all tags for blog posts and conversation participants in a chat. The data can be of Boolean, integer, float, characters, and other types. Static sets allow only query operations, which means operations related to querying the elements. Dynamic and mutable sets allow for the insertion and deletion of elements. Algebraic operations such as union, intersection, difference, and subset can be defined on the sets. The following example shows the Set integer with a map integer key and bool as a value:

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main
// importing fmt package
import (
 "fmt"
)
//Set class
type Set struct {
 integerMap...

Tuples

Tuples are finite ordered sequences of objects. They can contain a mixture of other data types and are used to group related data into a data structure. In a relational database, a tuple is a row of a table. Tuples have a fixed size compared to lists, and are also faster. A finite set of tuples in the relational database is referred to as a relation instance. A tuple can be assigned in a single statement, which is useful for swapping values. Lists usually contain values of the same data type, while tuples contain different data. For example, we can store a name, age, and favorite color of a user in a tuple. Tuples were covered in Chapter 1, Data Structures and Algorithms. The following sample shows a multi-valued expression from a function's call (tuples.go):

//main package has examples shown
 // in Hands-On Data Structures and algorithms with Go book
 package main
 ...

Queues

A queue consists of elements to be processed in a particular order or based on priority. A priority-based queue of orders is shown in the following code, structured as a heap. Operations such as enqueue, dequeue, and peek can be performed on queue. A queue is a linear data structure and a sequential collection. Elements are added to the end and are removed from the start of the collection. Queues are commonly used for storing tasks that need to be done, or incoming HTTP requests that need to be processed by a server. In real life, handling interruptions in real-time systems, call handling, and CPU task scheduling are good examples for using queues.

The following code shows the queue of Orders and how the Queue type is defined:

// Queue—Array of Orders Type
type Queue []*Order

// Order class
type Order struct {
    priority int
    quantity int
    product string
    customerName...

Stacks

A stack is a last in, first out structure in which items are added from the top. Stacks are used in parsers for solving maze algorithms. Push, pop, top, and get size are the typical operations that are allowed on stack data structures. Syntax parsing, backtracking, and compiling time memory management are some real-life scenarios where stacks can be used. An example of stack implementation is as follows (stack.go):

//main package has examples shown
// in Hands-On Data Structures and algorithms with Go book
package main
// importing fmt package
import (
 "fmt"
 "strconv"
)
//Element class
type Element struct {
 elementValue int
}
// String method on Element class
func (element *Element) String() string {
 return strconv.Itoa(element.elementValue)
}

The Element class has elementValue as an attribute. The String method returns the element's elementValue.

Stacks methods...

Summary

This chapter covered the definition of LinkedList, double LinkedList, Tuples, Sets, Queues, and Stacks. The LinkedList methods – AddToHead, AddToEnd, LastNode, and iterateList—were also covered in this chapter. In addition, a priority queue was modeled as a heap of orders to be processed, sync queue was presented as passenger and ticket processing queues, and tuples were explained in a context in which a function returns a multivalued expression. The new, push, pop, and string methods for Stack were explained with code samples.

In the next chapter, we will cover areas such as the Trees, Tables, Containers, and Hash functions.

Questions

1. Where can you use double linked list? Please provide an example.
2. Which method on linked list can be used for printing out node values?
3. Which queue was shown with channels from the Go language?
4. Write a method that returns multiple values. What data structure can be used for returning multiple values?
5. Can set have duplicate elements?
6. Write a code sample showing the union and intersection of two sets.
7. In a linked list, which method is used to find the node between two values?
8. We have elements that are not repeated and unique. What is the correct data structure that represents the collection?
9. In Go, how do you generate a random integer between the values 3 and 5?
10. Which method is called to check if an element of value 5 exists in the Set?

Further reading

To read more about LinkedLists, Sets, Tuples, and Stacks, consult the following sources:

• Design Patterns, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
• Introduction to Algorithms – Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Data structures and Algorithms: An Easy Introduction, by Rudolph Russell