Data structure

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In Computer Science, a data structure is a way of organizing information, so that it is easier to use. Data structures determine the way in which information can be used. If the focus of use is on the things that can be done, people often talk about an abstract data type (ADT). Data structures are often optimised for certain operations. Finding the best data structure when solving a problem is an important part of programming. Programs that use the right data structure are easier to write, and work better.

Basic data structures[change | edit source]

Array[change | edit source]

An array holds several values of the same kind. Accessing the elements is very fast. It may not be possible to add more values than defined at the start, without copying all values into a new array.

List[change | edit source]

A List can hold several values. Each item in the list has a way of telling where the next element is; some lists can also tell where the previous element is. It is very easy to add a new element at the start of the list; telling whether an element is already in the list is more difficult, and needs going through all elements of a list.

Stack[change | edit source]

A stack is like a list, but elements can only be added and removed at one end. In addition to adding ('push') or removing ('pop') an element, there's often an operation to look at top of the stack, without removing the element ('peek').

Queue[change | edit source]

A queue is a data structure,in which the elements can be added and removed from both the ends.

Graph[change | edit source]

A graph associates several elements. The elements are usually called vertices (one vertex, several vertices), the connections called edges.

Tree[change | edit source]

Trees are special Graphs, where there is only one way between any two vertices.