In this blog post, we will introduce the concept of data structure and explain why arrays and linked lists are important in an easy-to-understand manner.
Much time has passed since personal computers first appeared in the world. Back then, it was enough to have just one computer in the house, but today, not only computers but also smartphones, tablets, and even home appliances serve as computers. This change is not simply due to an increase in the number of devices, but also to the dramatic advancement in the performance and functionality of each device. As time has passed, the capacity of memory media has become incomparable to what it was in the early days, and processing speeds have become unimaginably fast. Moore’s Law, which is a law that explains this performance improvement, states that every 18 months, hardware integration doubles and performance doubles. This law has played an important role in predicting the development of the semiconductor industry, and as a result, the speed of hardware performance improvement has continued to grow at a remarkable rate. In accordance with this law, the memory capacity of personal computers, which used to be less than 10 MB, has become so large that terabytes are now commonplace. Today’s computers are capable of easily storing and processing hundreds of gigabytes of data, a level of advancement that scientists in the past could not have imagined. As memory devices become larger, it is necessary to consider how to use them efficiently. The method of using memory devices efficiently is called data structure.
To understand data structure and its necessity, it is first necessary to understand the structure of memory devices. A memory device consists of a set of small memory devices that can operate independently. This can be likened to a set of small lockers with serial numbers. Each locker can store a small amount of information, such as a few letters of the alphabet or a couple of numbers, and a group of these lockers make up the total memory space. Once each locker is assigned a unique number, it can be referenced by that number. Users only need to remember which locker their information is in, and they can retrieve or modify the desired information without having to search through all the other lockers. Understanding this structure is the first step in realizing the importance of data structures.
The need for data structures arises when memory devices are divided into small units. Since the size of lockers is not infinite, if the information you want to store is large, one locker will not be enough. For example, it would be impossible to store a list of all science and technology writing instructors in a single locker with only a few letters. In such cases, the information must be broken down into smaller pieces and stored in multiple lockers. When using multiple lockers, it would be much more efficient to remember only one or two serial numbers so that you can find all the lockers you have used, rather than randomly selecting empty lockers and remembering the serial numbers of all the lockers. In order to efficiently manage and process such complex information, it is essential to select an appropriate data structure. A good data structure is necessary to efficiently use multiple lockers. Numerous data structures have been developed through extensive research, and among them, the two most basic structures are arrays and linked lists.
An array is a structure that uses only lockers with consecutive numbers when using multiple lockers. In this structure, you can find all the lockers you have used by remembering only the number of the first locker and how many lockers you have used. Suppose that a user has used 10 lockers and that the first locker is number 2016. Then, we can immediately know that the user has used lockers 2016, 2017, 2018, …, 2024, and 2025. This structure requires only the first position and length to be remembered, so there is very little additional information to remember, no wasted space, and good space efficiency, and you can immediately know which locker is being used by the user. For example, in the previous example, you can immediately calculate that the fifth locker used by the user is locker number 2016 + 4 = 2020. This advantage of the array structure is particularly useful when the data does not occupy a large amount of space. However, if you want to delete information in the middle of the lockers in use, you have to move all the lockers after it forward one by one, which seriously reduces the efficiency of deleting information. Even if there are enough spare lockers, if they are not adjacent to each other, you cannot use all the remaining space.
A linked list is also a structure that can be used when you want to use multiple lockers. Unlike an array, a linked list does not use consecutive lockers, but instead stores the number of the next locker in each locker. This way, if you know the number of the first locker, you can see all the lockers you have used in order. Suppose that a user used lockers 100, 201, 43, and 1 in that order. Then, locker 100 contains the first piece of information and 201, locker 201 contains the second piece of information and 43, and locker 43 contains the third piece of information and 1. This characteristic of linked lists is particularly useful when data needs to be processed dynamically. The advantage of this structure is that as long as there are enough free lockers, all the information can be stored, and unlike arrays, information in the middle can be efficiently deleted when necessary. Suppose that the user wants to delete the information in box 43. All they have to do is open box 201 and change the 43 to 1. This flexibility makes linked lists very useful for handling variable data. However, the disadvantage of this structure is that it wastes space because each locker requires an additional number to be stored, and unlike arrays, it is not possible to immediately find the location of a locker, so you have to search through all the lockers from the beginning, which is inefficient.
Data structures are the foundation of many fields of computer science and are closely related to many problems in the real world. In fact, theories such as machine learning and big data, which are currently gaining popularity, are theories that deal with vast amounts of data, and these theories can only exist if there are good data structures that can handle large-scale data. As such, data structures go beyond simple theoretical concepts and are the foundation of the technology we use every day. Arrays and linked lists are the most basic data structures and form the basis of almost all other data structures. Understanding these two basic data structures is essential for handling complex data structures. It is necessary to understand these theories accurately from the ground up so that you can flexibly select the appropriate data structure for the situation and manage data. Furthermore, by studying the characteristics and applications of various data structures in depth, we will be able to solve more complex and diverse data processing problems.
