M. Daffa Syamsuddin
2301957603
In computer programming, an array of pointers is an indexed set of variables, where the variables are pointers (referencing a location in memory).
Pointers are an important tool in computer science for creating, using, and destroying all types of data structures. An array of pointers is useful for the same reason that all arrays are useful: it allows you to numerically index a large set of variables.
Linked List
Below is an array of pointers in C that points each pointer in one array to an integer in another array. The value of each integer is printed by dereferencing the pointers. In other words, this code prints the value in memory of where the pointers point.
Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have the following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.
A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.
One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
Another disadvantage is that a linked list uses more memory compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.
Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').
2301957603
Summary
Array and Pointers
Pointers are an important tool in computer science for creating, using, and destroying all types of data structures. An array of pointers is useful for the same reason that all arrays are useful: it allows you to numerically index a large set of variables.
Linked List
Below is an array of pointers in C that points each pointer in one array to an integer in another array. The value of each integer is printed by dereferencing the pointers. In other words, this code prints the value in memory of where the pointers point.
Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have the following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.
A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.
One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
Another disadvantage is that a linked list uses more memory compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.
Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').
Binary Tree
A binary tree is a tree data structure in which each node has at most two children,
which are referred to as the left child and the right child. It is implemented mainly using Links.
Binary Tree Representation
A tree is represented by a pointer to the topmost node in tree.
If the tree is empty, then value of root is NULL. A Binary Tree node contains following parts :
1. Data
2. Pointer to left child
3. Pointer to right child
Hashing Hash Function
A function that converts a given big input key to a small practical integer value.
The mapped integer value is used as an index in hash table.
A good hash function should have following properties.
1) Efficiently computable.
2) Should uniformly distribute the keys.
Hash Tree on Blockchain
A tree in which every leaf node is labelled with the cryptographic hash of a data block,
and every non-leaf node is labelled with the hash of the labels of its child nodes.
Example :
Source :
https://www.computerhope.com/jargon/a/array-of-pointers.html
https://en.wikipedia.org/wiki/Linked_list
https://www.geeksforgeeks.org/data-structures/linked-list/
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html
https://www.geeksforgeeks.org/overview-of-data-structures-set-2-binary-tree-bst-heap-and-hash/
https://en.wikipedia.org/wiki/Merkle_tree
Komentar
Posting Komentar