Bev Facey Community High

CSE 3320: Dynamic Data Structures 1

Students learn how to design, code and debug programs using abstract data types that utilize dynamic data structures. Students explore dynamic memory allocation, in general, and as handled by their programming environment. Students concentrate on how the linked list dynamic data structure(s) can be used to implement abstract data types.

• Prerequisite: CSE3310: Recursive Algorithms 1

Theory

Analyze and represent the nature, structure and utility of linked lists

1. describe and represent the nature of dynamic data structures including:
   • the mechanics of dynamic memory allocation; e.g., the heap, pointers and/or references, linear and non-linear data structures
   • a comparison and contrast of dynamic and static data structures
2. describe and represent the nature and mechanics of linked lists by:
   • describing linked lists as a components of abstract data types
   • describing the logical structure of the singly linear linked list including nodes, fields, references and pointers
   • describing the logical structure of other types of linked lists; e.g., double-linked, circularly-linked, ordered linked lists
3. describe and represent the operators associated with linked lists by:
   • creating the linked list
   • inserting a node
   • traversing the linked list
   • deleting a node
   • replacing a node
   • finding and retrieving data from the linked list
   • determining the size of the linked list
4. explain the advantages and disadvantages of the linked list over static data structures
   • include applications where you would prefer the use of linked lists over static data structures, and vice versa

Practical

These can all be done in most languages. Remember to use internal and external documentation in writing your code.

1. Build a linked list from scratch
   • Without using any built-in linked list features, construct a linked list with a standard linking type of your choice
   • The data type within your list is your choice
   • The program should contain functions to do the following:
     • Inserting a node at the end of the list, or after the n-th node in the list
       • This should return a pointer/reference to the inserted node.
     • Deleting the n-th node of the list
       • This should return a pointer/reference to the deleted node.
     • Replacing the n-th node of the list with a given value
       • This should return a pointer/reference to the inserted node.
     • Finding and retrieving data from the list
       • This should return a pointer/reference to the node containing the requested data.
     • Returning the size of the list
       • This should return an integer containing the size of the list.
     • Sorting the list by some attribute in your chosen data type
       • This should return a pointer/reference to the head of the list.
     • Merging two lists
       • This should return a pointer/reference to the head of the list.
     • Reversing the list
       • This should return a pointer/reference to the head of the list.
2. Design and write a program for a project involving the use of a linked list
   • Write a description of your intended project
   • Show evidence of planning your project
   • Submit the above along with any required program files to run your code

Competencies and Skills

You will also be evaluated on your basic competencies such as your ability to:

• communicate
• manage information
• use numbers
• think and solve problems
• demonstrate positive attitudes and behaviours
• be responsible
• be adaptable
• learn continuously
• work safely
• work with others
• participate in projects and tasks

This site is open source. Improve this page.