Data structure

Computer scientists recognize multiple kinds of data structures they use in their programs.

Some of the simpler data structures include:

• the stack
• the list
• the linked list
• the tree

Linked lists, and trees are built up of elements that are, themselves, data structures. Programmers use them when they know they need to keep track of very similar data, like individual credit card transactions, but they don't know how many instances there will be.

If credit card transactions were being kept track of, in a linked list, the underlying data structure that described a transaction would store the date of the transaction, the credit card number, the location where the transaction took place, and a brief description of the transaction, possibly one the item that was purchased. What makes it a linked list would be pointers to the next and previous items in the list.

Computer programs store data in local variables. Computer programmers merely have to declare that they need space for those local variables, when they write their programs. But since they don't know how many elements will be in a list, or tree, the memory used is acquired dynamically, the program signals it needs dynamically allocated memory, usually by making a call to the operating system, and a pointer to that memory is returned, and the program can then fill out its fields. In addition to the actual data describing the transaction there is space to point to the next and previous elements in the list. This allows linked lists to be maintained in sorted order. When a new credit card transaction occurs, after the element where its information is recorded, it can be slipped into its proper position in the list by changing the next and previous pointers of the elements it will be next and previous to.