What is a data structure?

Programming Answer

Click here to type your answer

Safarov answered

Data structure is an essential subject in programming, it's the way we organize and store data in our computers. The main goal is to find out the most effective data structure for a given task. The most popular ones are Arrays and Objects, but there many more.

In Learning data structure we first should start from abstract data types - it's the set of rules/methods defined from user's perspective, but implemented differently in each programming language. For example Queue, Stack, List is abstract data type, where Array is a concrete implementation exists in many languages. Although there is List implementation as well, but each language has it's own methods or semantics for List data type.

Here are few data types I have used:

1. Integer -  is used to contain whole numbers, can be positive, negative or zero. Also Integer data type can be grouped into unsigned and signed. Unsigned can contain only zero and positive whole numbers, where signed integer can contain negative integers as well. From implementations, I can note that in java there are two implementations "int" and "Integer" - first is a primitive data type, second one is class that is built around integer and have extra functionalities. In other words, "Integer" wraps "int" as an Object class.

2. Floating point - is used to store real numbers with decimal points. Can store negative values as well. As an example, In Java we have two primitive data types as an implementations, "double" and "float".  Float can contain numbers up to 4 bytes precision where "double" can store 2 times more - 8 bytes.

3. Boolean - is used to store Binary data more efficiently. Depending on implementation, Boolean can have values like 0 or 1, true or false, yes or no. It's mostly used for condition statements and logical expressions. Java has "boolean" and "Boolean" data types, first one is a primitive type and uses less memory, second one with capital "B" is a Object implementation, have more functionality, but make program slower (take more memory).

4. Enumerated type - is used to store list of constants in programming. An example would be colors in RBG as {Red, Green, Blue}. Some languages has ordered types another ones have unordered. Similarly some implementations is built-in (Java, C), for others you have to import library (Python). Also, for example in Javascript there isn't enum type, but higher language Typescript supports enum type.

5. List (Array) - is list of multiple elements to ease development. Generally implementations of List type, has following functionalities - create empty list, test how many elements list has, to be able to add or delete elements, read or update particular element at the specific index etc. The most well known implementation is an Array.

6. ArrayList or LinkedList - this is similar data type, some languages use ArrayList ( java, actionscript) , some languages like C uses LinkedList term. Basically the difference between LinkedList and List is: Elements of List are stored as a one chunk of data in the memory, but elements of LinkedList are stored separetely in memory, each element is pointing to the next one in the memory. This way Linked list is resizable (but lists aren't resizable), you can add as much elements as there is memory in system. But As you might guess, Lists are faster than LinkedLists and contain less space in memory, because program just need to store first element of list and length to get any element in the memory. There is also Doubly Linked List, only difference between LinkedList is Double LinkedList contains two pointers, first for previous node, another for next node. Where LinkedList you can't look-up previous node. In Doubly Linked List we are using extra memory, but we can perform some operations like deletion using less CPU cycles.

7. Stack - like a real world, stack works is a collection with you can get only last element inserted. In other words LIFO (last in first out) collection structure. It means you can only add element to the top, similarly only delete last element of stack. Other than you can check if stack is empty or not, and get last element of stack. Time complexity of operations are constant time O(1), which make very efficient to solve certain problems like recursion, string validation etc.

8. Queues - this is another way of store list of elements where what's inserted first, gets out first. It's also called FIFO (first-in-first-out). You can think of it as a Queue of people waiting to but tickets. Here we insert elements to tail of queue, but we remove first element that has been added. Also we can get first element of queue and check if there is any element left in queue. Similar to Stack we have constant time complexity for all of those operations. In programming sometimes we have some resource shared by multiple programs (or Threads), we use queue to store all of requests, so later we can perform operations one by one. 

9. Trees - generally we use to store elements that have hierarchy. The main difference between Trees and Types in 1-8, it's not linear. You can think of a Family Tree, where you have parent and siblings. Usually we use this structure when we want search if siblings have common parent, if yes, what node is that. This kind of grouping helps use to touch memory less when reading data, but it's a little bit complex when we are adding data. There is special kind of tree called Binary Tree where each node can have maximum 2 child elements.

10. Graphs - you can think of a Graph as a general tree where you don't have parent - sibling relation between nodes, and no restriction exists on the count of edges. We can say all of Trees are Graphs, but only subset of Graphs are Trees. There two kind of graphs Directed and Undirected. In directed Graph we store the direction of relation between nodes. World Wide Web, Social Network or Internet can be an example of a Graph. Another common problem where Graph is generally used is Transportation problem- Economists trying to find the cheapest route to transport goods.

0 points