What is ADT? (Abstract Data Type)

The Abstact data type Wikipedia article has a lot to say.

In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly cost) of those operations.

In slightly more concrete terms, you can take Java’s List interface as an example. The interface doesn’t explicitly define any behavior at all because there is no concrete List class. The interface only defines a set of methods that other classes (e.g. ArrayList and LinkedList) must implement in order to be considered a List.

A collection is another abstract data type. In the case of Java’s Collection interface, it’s even more abstract than List, since

The List interface places additional stipulations, beyond those specified in the Collection interface, on the contracts of the iterator, add, remove, equals, and hashCode methods.

A bag is also known as a multiset.

In mathematics, the notion of multiset (or bag) is a generalization of the notion of set in which members are allowed to appear more than once. For example, there is a unique set that contains the elements a and b and no others, but there are many multisets with this property, such as the multiset that contains two copies of a and one of b or the multiset that contains three copies of both a and b.

In Java, a Bag would be a collection that implements a very simple interface. You only need to be able to add items to a bag, check its size, and iterate over the items it contains. See Bag.java for an example implementation (from Sedgewick & Wayne’s Algorithms 4th edition).

Related Posts:

  1. What is dependency injection?
  2. What’s the difference between passing by reference vs. passing by value?
  3. What is the maximum number of weekdays in a year? How would you code it?
  4. “Parameter” vs “Argument”
  5. What’s the difference between a method and a function?
  6. What is the difference between a framework and a library?
  7. what does “nulled script” mean?
  8. What is a coroutine?
  9. What is an ORM, how does it work, and how should I use one? [closed]
  10. Converting bytes to megabytes
  11. What is an idempotent operation?
  12. What and where are the stack and heap?
  13. What is tail recursion?
  14. What is a race condition?
  15. What is a callback function?
  16. What is a loop invariant?
  17. What is a loop invariant?
  18. What is reflection and why is it useful?
  19. What is boilerplate code?
  20. What exactly is the difference between “pass by reference” in C and in C++?
  21. What do < and > stand for?
  22. IOException: The process cannot access the file ‘file path’ because it is being used by another process
  23. What is JSONP, and why was it created?
  24. What does it mean if a Python object is “subscriptable” or not?
  25. What is Bit Masking?
  26. What are bitwise shift (bit-shift) operators and how do they work?
  27. What is the difference between a deep copy and a shallow copy?
  28. What does it mean if a Python object is “subscriptable” or not?
  29. What is the difference between tree depth and height?
  30. What is the meaning of the term “thread-safe”?
  31. What is null in Java?
  32. Calculating a 2D Vector’s Cross Product
  33. What is the difference between concurrency and parallelism?
  34. What is stability in sorting algorithms and why is it important?
  35. What is an “internal error” and how do I fix it?
  36. How Does Modulus Divison Work
  37. Array versus linked-list
  38. What is a clock cycle and clock speed?
  39. What exactly is GUID? Why and where I should use it?
  40. Difference between ‘cls’ and ‘self’ in Python classes?
  41. What is the function of the push / pop instructions used on registers in x86 assembly?
  42. What is the difference between application server and web server?
  43. What is an invariant?
  44. What is “runtime”?
  45. Prefer composition over inheritance?
  46. Are there dictionaries in php?
  47. What is the difference between memoization and dynamic programming?
  48. What are sessions? How do they work?
  49. What is the difference between UTF-8 and Unicode?
  50. What is spaghetti code?
  51. What is the difference between a web API and a web service?
  52. What is the meaning of “exclusive” and “inclusive” when describing number ranges?
  53. What do Push and Pop mean for Stacks?
  54. What is tail call optimization?
  55. What is a “meta component” in the context of bootstrap or as a general web design term?
  56. What is the difference between a map and a dictionary?
  57. Definition of a Java Container
  58. What is meant by diameter of a network?
  59. What is a good Hash Function?
  60. What is runtime in context of Python? What does it consist of?
  61. Why does cache locality matter for array performance?
  62. What is a loop invariant?
  63. What is the difference between an Abstract Data Type(ADT) and a Data Structure?
  64. What is a class constant?
  65. What is an anti-pattern?
  66. Inheritance vs. Aggregation [closed]
  67. Is there an O(n) integer sorting algorithm?
  68. What does ‘foo’ really mean? [closed]
  69. Javascript: difference between a statement and an expression?
  70. Create your own MD5 collisions
  71. What is the difference between bucket sort and radix sort?
  72. What’s the difference between a word and byte?
  73. What is the best regular expression to check if a string is a valid URL?
  74. Finding all possible combinations of numbers to reach a given sum
  75. Converting EBNF to BNF
  76. What are MVP and MVC and what is the difference?

Leave a Comment