Computer Science - Data Structures

Data Structures Search for a string, average a column

Tuesday, February 17, 2009 2:04 PM

Arrays: - 1 and 2 dimensional, store a list and a table respectively. - Stores multiple data of the same type with 1 variable name (uses an array index) - e.g. table[3][4];, 3 is row, 4 is column. - Must be declared before used. - Array size in Java is static, (it may be an inefficient use of RAM). - Data is erased in the end of runtime. Linked List File: - A linked list is a linear collection (ie a sequence) of self-referential class - Store data in a separate file (text) objects, called nodes, connected by reference links - hence, the term - Read and write to the file "linked" list. - Permanent data storage - A program references a linked list via a reference to the first node of the list. The program accesses each subsequent node via the link reference stored in the previous node. Linked List - By convention, the link reference in the last node of a list is set to null - Collections of data items "lined up in a row" to mark the end of the list. - Insertions and deletions can be made anywhere in a linked list. - The list creates each node as necessary. This is useful when the number of data elements to be represented in the data structure is Stacks unpredictable. - Important in compilers an operating systems. - Linked lists can be maintained in sorted order simply by inserting each - Insertions and deletions are made only at one end of a stack - it's new element at the proper point in the list. top. - Linked list nodes normally are not stored contiguously in memory. Rather they are logically contiguous. Each node contains a reference to Queues the next node in the list. - Represent waiting lines - Insertions are made at the back tail) of the queue and deletions are made from the front (head of the queue). Binary trees - Facilitate high-speed searching and sorting of data, elimination of duplicate data items efficiently, representing file system directories, compiling expressions into machine language.

Queues - A queue is similar to a checkout line in a grocery store - the cashier services the person at the beginning of the line first. Other customers enter the line only at the end and wait for service. - Queue nodes are removed only from the head (or front) of the queue and are inserted only at the tail (or edn) of the queue. - For the reason a queue is a first-in, first-out (FIFO) data structure. The insert and remove operations are known as enqueue and dequeue. - Most compilers have a single processor, so only one application at a time can be serviced. Entries for the other applications are place in a queue. The entry at the front of the queue is the next to receive service. Each entry gradually advances to the front of the queue. - Events such as keystrokes and mouse clicks are stored in a queue. A program removes events from the queue and process them. It's possible for several more events to occur while one event is being process, but since the events are stored in a queue, the will always be processed in the order they occurred.

Stacks - A stack consists of a sequence of items, which should be thought of piled one on top o the other like a physical stack of boxes or cafeteria trays. Only the top item on the stack is acccessible at any given time. - A stack is a constrained version of a linked list - new nodes can be added to a stack and removed from a stack only at the top. For this reason, a stack is referred to as a last-in, first out (LIFO) data structure. The link member in the bottom (ie last) node of the stack is set to null to indicate the bottom of the stack. - The primary methods used to manipulate a stack are push and pop. Method push adds a new node at the top of the stack. Method pop removes a node from the top of the stack and returns the data from the popped node. Application of Stacks - For example when a program calls a method, the called method must know how to return to its caller, so the return address of the calling method is pushed onto the program execution stack. - If a series of method calls occurs, the successive return addresses are pushed onto the stack in a last-in first out order so that each method can return to its caller. - The program execution stack contains the memory for local variables on each invocation of a method during the program's execution. When the method returns to its called, the memory for that method's local variables is popped off the stack and those variables are no longer known to the program. - Compilers use stacks to evaluate arithmetic expressions an generate machine language code to process the expressions. - When a compiler checks for balancing of ( ), { }, [ ] in computer programs, it implements a stack. - Page swapping as temporary data holder.

Computer Science Page 1