what is a Data Structure and a discussing some of its applications
A data structure is a particular way of organizing data in a computer so that it can be used effectively.
For example, we can store a list of items having the same data type using the array data structure.
We can also define it simply as a collection of data elements in some organized fashion.
In other words, the data structures consist of a set of nodes that contain the necessary data items or elements that are needed by computer applications.
and there is the following point to remember:
- Each node (data element) may be represented by one computer word or several words in the memory of the computer system.
As we know a memory consists of cells called words: with sizes 1,2, 4, and 8 bytes.
What is a Node
Node (item or element):
- An Element or item of the data structure is called (node). Thus a data structure consists of a set of nodes.
- The data at each node is represented by one word or more.
A data structure Example
- list of names of customers.
1# 2# ---------------------------------------------- 3# List | Ali | Omar | Anas | Badr | Ebrahim | 4# ---------------------------------------------- 5# Index 0 1 2 3 4 6#
Node address
Each node has some address (memory location of its first word), It is called a link, pointer, or reference.
The address may be:
- absolute address (10, for example).
- relative to some base address (base + R)
Basic Operations on nodes
Note:
- I will use the index instead of address.
- index will always start from 0.
Accessing
Finding the position of some node to get its content or change the content.
For example Print name in the index of 3 in the list of names of customers.
1# 2# ---------------------------------------------- 3# List | Ali | Omar | Anas | Badr | Ebrahim | 4# ---------------------------------------------- 5# Index 0 1 2 3 4 6# 7# ^^^^^^^^
Index three contains "Badr".
Inserting
In some cases, a new node may be inserted into the data structure
For example, inserting the name "Baher" in list of names of customers in the end, will give the following structure.
1# 2# Before inserting: 3# ---------------------------------------------- 4# List | Ali | Omar | Anas | Badr | Ebrahim | 5# ---------------------------------------------- 6# Index 0 1 2 3 4 7# 8# After inserting: 9# ------------------------------------------------------- 10# List | Ali | Omar | Anas | Badr | Ebrahim | Baher | 11# ------------------------------------------------------- 12# Index 0 1 2 3 4 5 13#
Deletion
In some cases, we may delete some nodes for some reason.
For example, deleting the node containing the name "Anas" in list of names of customers gives the following data structure.
1# 2# Before deletion 3# ------------------------------------------------------- 4# List | Ali | Omar | Anas | Badr | Ebrahim | Baher | 5# ------------------------------------------------------- 6# Index 0 1 2 3 4 5 7# ^^^^^^^^ 8# 9# 10# After deletion 11# ---------------------------------------------- 12# List | Ali | Omar | Badr | Ebrahim | Baher | 13# ---------------------------------------------- 14# Index 0 1 2 3 4 15#
we will have to first search for it is located before deleting it.
Searching
Finding some node with a certain value, for example: find the index of the node in the given data structure containing the name "Badr" in list of names of customers.
1# 2# ---------------------------------------------- 3# List | Ali | Omar | Badr | Ebrahim | Baher | 4# ---------------------------------------------- 5# Index 0 1 2 3 4 6# ^^^^^^^^ 7#
the name "Badr" is in the index of 2.
Sorting
Sorting of nodes is done based on some key (ascending or descending).
For example, sorting the list of names of customers alphabetically descending.
1# 2# Before sorting: 3# ---------------------------------------------- 4# List | Ali | Omar | Badr | Ebrahim | Baher | 5# ---------------------------------------------- 6# Index 0 1 2 3 4 7# 8# After sorting: 9# ---------------------------------------------- 10# List | Ali | Badr | Baher | Ebrahim | Omar | 11# ---------------------------------------------- 12# Index 0 1 2 3 4 13#
Copying
The whole structure or some part of It may be copied into another structure.
For example, coping that starts with the letter "B" from the list of names of customers and create a new list named list of names of customers B
1# 2# List of names of customers: 3# ---------------------------------------------- 4# List | Ali | Badr | Baher | Ebrahim | Omar | 5# ---------------------------------------------- 6# Index 0 1 2 3 4 7# 8# list of names of customers B 9# ------------------ 10# List | Badr | Baher | 11# ------------------ 12# Index 0 1 13
Combining and splitting (separating)
Combining means that two or more structures can be joined into a single structure.
Splitting is the inverse operation of combining.
for example, splitting the list of names of customers B to two half's and then adding the second half to the first to the list of names of customers
1# 2# List of names of customers: 3# ---------------------------------------------- 4# List | Ali | Badr | Baher | Ebrahim | Omar | 5# ---------------------------------------------- 6# Index 0 1 2 3 4 7# 8# List of names of customers B before splitting 9# ------------------ 10# List | Badr | Baher | 11# ------------------ 12# Index 0 1 13# 14# 15# (1) List of names of customers B after splitting 16# 17# 18# -------- 19# List (first half) | Badr | 20# -------- 21# Index 0 22# 23# --------- 24# List (second half) | Baher | 25# --------- 26# Index 0 27# 28# (2) Adding the second half to the first to the _list of names of customers_ 29# 30# -------------------------------------------------------- 31# List | Ali | Badr | Baher | Ebrahim | Omar | Baher | 32# -------------------------------------------------------- 33# Index 0 1 2 3 4 5 34# ^^^^^^^^^ 35#