Data structures and algorithms – Simple data structures

preface

In the opening section of data structures and Algorithms, we learned some basic concepts of data structures.

• A data structure is a storage structure for a group of data, and an algorithm is a method for manipulating data.
• Data structures serve algorithms that operate on a particular data structure.
• Data structures and algorithms solve the problem of how to store and process data more cheaply and quickly. I have only understood the basic concepts of data structures before, but this article will focus on in-depth understanding of data structures.

Terminology for data structures

• ** Data: ** Data not only represents the common data information such as integers and strings, but also can be used to represent sound, image, video and other information. In fact, everything that can be put into a computer and processed correctly by a computer is data.
• ** Data element: ** is the basic unit of data, usually considered as a whole.
• Data items: A data element can consist of several data items. A data item is the smallest indivisible unit of data. But when you really talk about the problem, it’s the data elements that are the focus of the data model in the data structure.
• ** Data object: ** is a collection of data elements of the same nature. It is a subset of data.
• ** Data structure: ** is a collection of data elements that have one or more specific relationships with each other.

In a computer, data elements are not isolated and disorderly, but intrinsically related data sets. The organization of data in one or more specific relationships between data elements.

• ** Structure: ** refers to the way the components fit together and are arranged. The simple way to think about it is relationships, like molecular structure, which means the arrangement of the atoms that make up a molecule.

Logical structure and physical structure

In fact, data structures distinguish logical structures from physical structures. The physical structure is actually the actual storage structure of the data structure, but it is not necessarily logically the same as the storage structure. The physical structure is usually array and linked list. Array and linked list are the most basic data structures. For example, queue is called sequential queue if it is based on array implementation, and chained queue if it is based on linked list implementation. The logical structure and physical structure are discussed in detail.

Logical structure

Logical structure refers to the relationship between data elements in a data object. There are four types of logical structures:

1. ** Collection structure: data elements in a collection structure have no relationship other than that they belong to the same collection. Each data element is “equal”, and the common attribute is “belong to the same set”. Set relations are similar to sets in mathematics. Arrays, linked lists, hash tables.
2. ** Linear structures: ** Linear structures have one-to-one relationships between data elements. Queue, stack.
3. ** Tree structure: ** There is a one-to-many hierarchical relationship between data elements in a tree structure. The tree.
4. ** Graphic structure: ** The data elements of a graphic structure are many-to-many relationships. Figure.

Logical structure is for specific problems, is to solve a problem, on the basis of understanding the problem, choose a suitable data structure to represent the logical relationship between data elements.

The physical structure

Data is a collection of data elements, which, by definition of physical structure, is actually how the data elements are stored in the memory of the computer. The data storage structure should correctly reflect the logical relationships between data elements. There are two storage structures for data elements:

• ** Sequential storage structure: ** stores data elements in storage units with contiguous addresses. The logical and physical relationships between data are consistent. It’s essentially an array-based data structure
• ** Chain storage: ** stores data elements in arbitrary storage units, which can be contiguous or discontiguous. The storage relation of data elements cannot reflect its logical relation. A pointer is needed to store the address of data elements, through which the location of associated data elements can be found. It is essentially a data structure based on linked list implementation.

Logical structure is problem oriented, while physical structure is computer oriented, and its basic goal is to store data and its logical relationships in the memory of the computer.

Abstract data type

• Abstract data type (ADT) is an abstract representation of a data structure that simply states which interfaces are supported and which concrete data structure implementations must follow.
• Abstract data types only regulate the interface, not the implementation details, nor the language in which they are implemented.
• The definition of an abstract data type depends only on its set of logical properties, not on how it is represented and implemented inside the computer.
• An abstract data type defines a data object, the relationships among the data elements in the data object, and operations on the data elements.

Compare abstract data types defined in Java:

Linear and nonlinear tables

The linear table

• Linear tables are the most basic, simplest, and most commonly used data structures. A linear list is a type of data structure. A linear list is a finite sequence of n data elements having the same properties.
• The relationship between data elements in a linear table is one-to-one, that is, all data elements are end to end except the first and last data elements (note that this applies only to most linear tables, not all. For example, a circular linked list is also a linear list at the logical level (the storage level is chained, but the last data element’s tail pointer points to the first node).
• In the logical level of data structure subdivision, linear table can be divided into general linear table and restricted linear table. A general linear table, also known as a “linear table”, is free to delete or add nodes. Constrained linear tables mainly include stacks and queues, and constrained means that operations on nodes are limited.

Nonlinear table

Any table that does not meet the characteristics of a linear table is a nonlinear table, such as a tree, graph, hash table.