Data Structures In Java

[anitsh]

Data type: a set of values together with operations (specified as input-output behavior) Data structure: a physical implementation of a data type

A data structure is a mathematical object with some set of properties that can be realized in many different ways as data types. A data type is just a class of values that can be concretely constructed and represented. A data model is an abstract model that organizes elements of data and standardizes how they relate to one another and to the properties of real-world entities. For instance, a data model may specify that the data element representing a car be composed of a number of other elements which, in turn, represent the color and size of the car and define its owner.

A symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier (or symbol) in a program's source code is associated with information relating to its declaration or appearance in the source. In other words, the entries of a symbol table store the information related to the entry's corresponding symbol.

Memory

Bit. 0 or 1. Byte. 8 bits. Megabyte (MB). 1 million or 2^20 bytes. Gigabyte (GB). 1 billion or 2^30 bytes.

In 64-bit machine with 8 byte pointers. ・ Can address more memory. ・ Pointers use more space. Some Java Virtual Machines compress ordinary object pointers to 4 bytes to avoid this cost.

Data Types

A data type is an attribute of a variable which tells the compiler or interpreter how the programmer intends to use the variable. It defines the operations that can be done on the data and what type of values can be stored.

Primitive Data Types

A primitive data type is pre-defined by the programming language. The size and type of variable values are specified, and it has no additional methods. These are value types.

Non Primitive Data Types

Non-Primitive data types refer to objects and hence they are called reference types.

One Dimensional Array	Memory ( Bytes )
char[]	2N + 24
int[]	4N + 24
double[]	8N + 24

Two Dimensional Arrays	Memory ( Bytes )
char[][]	~ 2 M N
int[][]	~ 4 M N
double[][]	~ 8 M N

Data Structures In Computer Science

• Essential : Lists, Arrays, Sets, Trees, and Maps
• Advance : Heaps, Tries, Doubly-Linked Lists, Union-Find, and for bonus points self-balancing binary trees.

Arrays and linked lists are the building blocks for these more complex data structures.

Reference

454 Advance Data Structure

Resource

• https://en.wikipedia.org/wiki/Data_structure
• http://www.andrew.cmu.edu/course/15-121 | https://www.cs.cmu.edu/~adamchik/15-121/lectures
• https://www.cs.cmu.edu/~adamchik/15-121/lectures | http://cslibrary.stanford.edu/102 Memory and Pointers
• https://cs.lmu.edu/~ray/notes/dtds
• https://algs4.cs.princeton.edu/14analysis
• https://www.interviewcake.com/article/python/data-structures-coding-interview
• https://www.hackerearth.com/practice/data-structures
• https://datastructures.maximal.io
• https://www.data-structures-in-practice.com
• https://www.tutorialspoint.com/abstract-data-type-in-data-structures
• https://www.edureka.co/blog/data-types-in-java
• https://stackoverflow.com/questions/4630377/explain-the-difference-between-a-data-structure-and-a-data-type
• [ ] https://www.freecodecamp.org/news/learn-all-about-data-structures-used-in-computer-science
• [ ] https://blog.bitsrc.io/data-structures-you-should-know-as-a-javascript-developer-9a35eb3b319c
• [x] B-Tree & Log Structured Merge (LSM) Tree use case : https://medium.com/yugabyte/a-busy-developers-guide-to-database-storage-engines-the-basics-6ce0a3841e59
• [ ] https://blog.pragmaticengineer.com/data-structures-and-algorithms-i-actually-used-day-to-day
• [ ] https://en.wikipedia.org/wiki/Data_model
• [ ] https://en.wikipedia.org/wiki/Symbol_table

[anitsh]

HashMap

• https://en.wikipedia.org/wiki/Hash_table
• https://www.interviewcake.com/concept/java/hash-map

[anitsh]

Trees

• https://en.wikipedia.org/wiki/Tree_(data_structure)
• https://en.wikipedia.org/wiki/Binary_tree
• http://cslibrary.stanford.edu/110/BinaryTrees.html
• https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html
• https://www.hackerearth.com/practice/data-structures/trees
• https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder
• https://www.geeksforgeeks.org/level-order-tree-traversal
• https://blog.tensorflow.org/2021/05/introducing-tensorflow-decision-forests.html

[anitsh]

Heap Data Structure

We form a binary tree with certain properties: The elements of L are placed on the nodes of the tree; each node holds one element and each element is placed on one node. The tree is balanced which as far as I'm concerned means that all paths have length O(log n); Baase uses a stronger property in which no two paths to a leaf differ in length by more than one. (The heap property): If one node is a parent of another, the value at the parent is always smaller than the value at the child.

You can think of the heap property as being similar to a property of family trees -- a parent's birthday is always earlier than his or her childrens' birthdays. As another example, in a corporate hierarchy, the salary of a boss is (almost) always bigger than that of his or her underlings.