Data Structures - Computer Science

Data Structures - Computer Science

Data Structures Simple data type int, char, long Reference data type Integer, String, Composite data type == Data Structure Collection of elements of possibly different types Class Linear Data Structures

Elements have an order Each element has a predecessor and a successor One element is first, and one is last Examples: List Stack Queue Hierarchical Data Structures Elements relate in 1:many relationships Trees

One root at the base of the structure One or more leaves most distant from the root 0, 1, or many internal nodes (neither root, nor leaf) Each node has: a unique predecessor, and 0, 1, or many successors Graph Data Structure Elements may have many:many relationships with other elements No constraints on numbers of predecessors

or successors Arrays [0] 8 [1] [2] [3] [4]

[5] [6] [7] advantages: Create one of any size while the program is running. Efficient; only overhead is store Addr. of a[0] + length. 2*element-size Constant-time element access.

Addr. of a[2] Whats not to like? Lists An ordered collection of nodes Node contains: Information (data) Identity of the successor (next) Identity of the predecessor (previous) List Operations/Methods

first()

last() next() previous() add() / add( pos ) remove() / remove( pos ) append() get() / get( pos ) set() / set( pos ) exists() /contains() /isOnList()

size() Linked List advantages: Starts empty; grows as things are added no wasted space. Insertion / removal from front in constant time From Prof. Heliotis, 2006

Link Nodes, Basic Types class LinkNode { int value; LinkNode next; LinkNode( int v ) { value = v; } // other methods... }; new LinkNode( 7 ) 7

From Prof. Heliotis, 2006 Link Nodes, Generic Contents class LinkNode { E value; LinkNode next; LinkNode( E v ) { value = v; } // other methods... }; new LinkNode( obj )

HeartObj From Prof. Heliotis, 2006 Insert insertAfter( a, c ); a X b c From Prof. Heliotis, 2006

Deletion remove( c ); a b c Where is a? From Prof. Heliotis, 2006 Deletion, Take 2 removeNodeFollowing( a ); a

X b c From Prof. Heliotis, 2006 Doubly Linked Lists (code) class DLinkNode { int value; DLinkNode previous, next; DLinkNode( int v ) {

value = v; } // other methods... }; From Prof. Heliotis, 2006 Doubly Linked Lists Now it is possible to directly delete a link node! From Prof. Heliotis, 2006 A LinkedList Class, Take 1

class LinkedList { LinkNode start; }; start From Prof. Heliotis, 2006 A LinkedList Class, Take 2 class LinkedList2 { LinkNode start; LinkNode end; };

From Prof. Heliotis, 2006 start end A LinkedList Class, Take 3 class DLinkedList { DLinkNode start; DLinkNode end; }; start end

From Prof. Heliotis, 2006 Class Exercise/Discussion What would a linked lists responsibilities be? What specific methods might it implement? How would you implement insertion? (singly linked list) How would you implement removal? (singly linked list)

Recently Viewed Presentations

  • Colonial America 1587 to 1770 - Leon County Schools

    Colonial America 1587 to 1770 - Leon County Schools

    South Returns to U.S. Congress. In 1865, many of the Southern states elected new government officials and sent them to Washington, D.C. They included many former Confederate leaders.
  • Our Future - University of Pittsburgh

    Our Future - University of Pittsburgh

    Our Future Christine Yoshinaga-Itano, Ph.D. University of Colorado, Boulder Department of Speech, Language & Hearing Sciences What's changed Almost every birthing hospital in the US has instituted a newborn hearing screening program.
  • Practical Clin Path Hemolytic Anemia Wendy Blount, DVM

    Practical Clin Path Hemolytic Anemia Wendy Blount, DVM

    50% FeLV or FIV positive. Splenomegaly common. PCR is available and a good test, but presence of organism does not always result in disease. Make smears immediately after capillary blood collection 9 (ear prick, lip prick) Organisms detach with time....
  • Metanephredia of Earthworm - University of Miami

    Metanephredia of Earthworm - University of Miami

    Protonephridia Metanephredia of Earthworm Roles of the Kidney Filtration -- 180 liters/day of water, all NaCl, sugar, amino acids Absorption -- 178.5 liters reabsorbed with 95-99% of NaCl, all glucose, amino acids Secretion -- acids and bases, toxins, antibiotics Concentration...
  • Pharmacy Systems Work Group: Conclusions and Recommendations

    Pharmacy Systems Work Group: Conclusions and Recommendations

    Bob A. Rappaport, M.D. Director Division of Anesthesia, Analgesia, and Addiction Products CDER, FDA 1st Scientific Workshop Analgesic Clinical Trial Innovations, Opportunities, and Networks an FDA Public-Private Partnership June 15, 2011 FDA White Oak Campus
  • Facilitating Student Dialogue

    Facilitating Student Dialogue

    Susan Crosson - Santa Fe Community College [email protected]u Andy Williams - Edmonds Community College [email protected] Communication with Students "Why don't they get it?" "If they would just follow the instructions…." "Can't they read?" "Why are they taking an online class,...
  • Rubrics - k-state.edu

    Rubrics - k-state.edu

    A strong rubric will provide clear descriptions of how each evaluative criterion is applied, so that, with reasonable training, different rubric users will come up with essentially the same evaluations for student work. A weak rubric's evaluative criteria will lead...
  • Ashtabula Williams Lucas Fulton Lake Geauga Wood Henry

    Ashtabula Williams Lucas Fulton Lake Geauga Wood Henry

    Jackie Wilkins Created Date: 6/3/1996 2:38:14 AM Document presentation format: On-screen Show (4:3) Other titles: Times New Roman MS Pゴシック Arial Calibri Office Theme 1_Office Theme 2_Office Theme 3_Office Theme 4_Office Theme 5_Office Theme 6_Office Theme 7_Office Theme 8_Office Theme...