Data structures: Wikis

Advertisements
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

(Redirected to Data structure article)

From Wikipedia, the free encyclopedia

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.[1][2]

Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers.

Data structures are used in almost every program or software system. Specific data structures are essential ingredients of many efficient algorithms, and make possible the management of huge amounts of data, such as large databases and internet indexing services. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design.

Contents

Basic principles

Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by an address — a bit string that can be itself stored in memory and manipulated by the program. Thus the record and array data structures are based on computing the addresses of data items with arithmetic operations; while the linked data structures are based on storing addresses of data items within the structure itself. Many data structures use both principles, sometimes combined in non-trivial ways (as in XOR linking).

Abstract data structures

The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analyzed separately from those operations.

This observation motivates the theoretical concept of an abstract data type, a data structure that is defined indirectly by the operations that may be performed on it, and the mathematical properties of those operations (including their space and time cost).

Language support

Assembly languages and some low-level languages, such as BCPL, generally lack support for data structures. Many high-level programming languages, on the other hand, have special syntax or other built-in support for certain data structures, such as vectors (one-dimensional arrays) in the C programming language, multi-dimensional arrays in Pascal, linked lists in Common Lisp, and hash tables in Perl. Many languages also provide basic facilities such as references and the definition record data types, that programmers can use to build arbitrarily complex structures.

Most programming languages feature some sort of library mechanism that allows data structure implementations to be reused by different programs. Modern programming languages usually come with standard libraries that implement the most common data structures. Examples are the C++ Standard Template Library, the Java Collections Framework, and Microsoft's .NET Framework.

Modern languages also generally support modular programming, the separation between the interface of a library module and its implementation. Some provide opaque data types that allow clients to hide implementation details. Object-oriented programming languages, such as C++, .NET Framework and Java, use classes for this purpose.

With the advent of multi-core processors, many known data structures have concurrent versions that allow multiple computing threads to access the data structure simultaneously.

See also

References

  1. ^ Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 15 December 2004. Online version Accessed 2009-05-21.
  2. ^ Entry data structure in the Encyclopædia Britannica (2009) Online entry accessed on 2009-05-21.
  • Niklaus Wirth, Algorithms and Data Structures
  • Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley.
  • Dinesh Metha and Sartaj Sahni Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 2007.

External links

Advertisements

Study guide

Up to date as of January 14, 2010

From Wikiversity

Data structures help you organize and process your data. There are many different ways of implementing them depending on available resources and whims of the programmer, but here are the general ideas behind them:

Contents

Choosing a Data Structure

The type of data structure you want to use will often be determined by how quickly you need to be able to do certain things to the data and how often, with compromises sometimes made for hardware or network restrictions.

Linked lists

Think of a linked list as a series of boxes(called nodes) in a row. Each piece of information (or set of information) is put into one box with a pointer to the next box. A doubly linked list is one that also has pointers that go back the other way to the previous box. They have head and tail pointers to help you keep track of where the beginning and end are, and usually at least one pointer that moves around the inside of the structure to point at a box to help you keep your place as you look for things.

/*needs pictures*/

For example, suppose you wanted to keep the names, addresses, and birthdays of your friends in a linked list. Each node would have one friend's name, address, and birthday in it, plus a pointer to the next in the list. If you want, the list can be sorted as you add friends to it, based on their name, address, or birthday in whatever way you want. If you know that some friends are more important to you and you don't want to go through the whole list to look for them every time, you can add in another variable for each person that can be used to set a sorting priority.

Queues

A Queue is a data structure that provides first-in-first-out access to elements. The two basic operations are Enqueue() and Dequeue(). Enqueue() adds an element to the back of the Queue. Dequeue() removes an element from the front of the queue. Just like a line at the supermarket, a Queue only supports adding items to the back and removing them from the front. In addition, some implementations allow you to 'peek' at the item in front without removing it.

/*needs pictures*/

Stacks

A stack is a data structure that supports first-in-last-out access to elements, meaning the most recently added element is the first to be removed. Stacks have two main operations, namely Push() and Pop(). Push() adds an element to the top of the stack, while Pop() removes the element at the top of the stack. You can think of it as a stack of plates: you can 'push' additional items onto the stack of plates or 'pop' plates from the top of the stack.

Stacks are usually implemented through a linked list.

/*needs pictures*/

Trees

You can think of a tree structure as a linked list with more than one outgoing pointer per node. This way, it branches out and the ends are called leaves instead of tails. The top node is called the root and the branches, like a real tree, don't merge back together. Thus, the nodes all have one incoming pointer and zero or more outgoing pointers, depending on the type of tree, its location within it, and the set of data that is shaping the tree.

Binary Trees

A binary tree is a specific type of tree with 0, 1, or 2 child nodes.

Traversal techniques

There are three main ways to process data in a tree. Recursion is usually the simplest way to perform such a task, where "traverse left" and "traverse right" below are recursive functions calls with the left and right children, respectively.

Preorder: process node, traverse left, traverse right

Inorder: traverse left, process node, traverse right

Postorder: traverse left, traverse right, process node

For example, consider the following recursive function to display the elements in a tree:

Method Display(Node *ptrNode)
   if (ptrNode == NULL)
      return;
   Display(ptrNode->left);             //recursive function call with left child
   cout << ptrNode->value;             //display value at current node
   Display(ptrNode->right);            //recursive function call with left child
End Method

This is a simple Inorder traversal.

Binary equivalent of a generic tree

Graphs

  • Dijkstra's algorithm
  • Kruskal's algorithm

Hash tables

Dynamic Allocation

Dynamic allocation asks for memory as it is needed.


Wikibooks

Up to date as of January 23, 2010
(Redirected to Data Structures article)

From Wikibooks, the open-content textbooks collection

ComputerScienceDataStructuresCoverArt.png

This book is about the creation and analysis of efficient data structures. This book covers:

  • the primitive node structure;
  • asymptotic notation for mathematically discussing performance characteristics;
  • built-in arrays;
  • list structures built from either nodes or arrays;
  • iterators as an abstract model of enumerating the items in a sequence;
  • stacks and queues for computing with last-in/first-out and first-in/first-out orderings;
  • binary and general tree structures for searching or representing hierarchical relationships;
  • min and max heaps for representing ordering based on priorities;
  • graph structures for representing more general relationships between data elements;
  • hash tables for the efficient retrieval of strings and other objects; and finally
  • trade-offs between the structures, and strategies for picking the most appropriate ones.

To understand the material in this book you should be comfortable enough in a programming language to be able to work with and write your own variables, arithmetic expressions, if-else conditions, loops, subroutines (also known as functions), pointers (also known as references or object handles), structures (also known as records or classes), simple input and output, and simple recursion.

Because many different languages approach the construction of data structures differently, we use pseudo-code so that you can translate the code into your own language.

Contents

Table of Chapters

Why a book on Data Structures?

A wiki-book is an undertaking similar to an open-source software project: A contributor creates content for the project to help others, for personal enrichment, or to accomplish something for the contributor's own work (e.g., lecture preparation).

An open book, just like an open program, requires time to complete, but it can benefit greatly from even modest contributions from readers. For example you can fix "bugs" in the text (where the bug might be typographic, expository, technical, aesthetic or otherwise) in order to make a better book. If you find an opportunity to fix a bug, simply click on "edit", make your changes, and click on save. Other contributors may review your changes to be sure they are appropriate for the book. If you are unsure, you can visit the discussion page and ask there. Use common sense.

If you would like to make bigger contributions, you can take a look at the sections or chapters that are too short or otherwise need more work and start writing! Be sure to skim the rest of the book first in order to avoid duplication of content. Additionally, you should read the Guidelines for Contributors page for consistency tips and advice.

Note that you don't need to contribute everything at once. You can mark sections as "TODO," with a description of what remains to be done, and perhaps someone else will finish those parts for you. Once all TODO items are finished, we'll have reached our First Edition!

This book is intentionally kept narrow-in-focus in order to make contributions easier (because then the end-goal is clearer). This book is part one of a series of three computer science textbooks on algorithms, continuing on to the techniques of algorithms in Algorithms and ending with Advanced Data Structures and Algorithms. If you would like to contribute a topic not already listed in any of the three books try putting it in the Advanced book, which is more eclectic in nature. Or, if you think the topic is fundamental, you can go to either the Algorithms or the Data Structures discussion page and make a proposal.

Additionally, implementations of the algorithms (in either Ada, C, C#, Perl, Python, Java, Ruby, or Scheme) as an appendix are welcome.

Further Reading

The following books list Data Structures as a prerequisite:

References

The authors highly recommend the following reference materials.

[Aho] Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
[Knuth] Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.

Additionally, as an online reference to the scope of algorithms today: Dictionary of Algorithms


Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message