Neil Harding (you can read about him at https://www.programmingassignmentexperts.com/about.php) will be working on your data structure assignments. He has experience of providing help with programming assignments/projects for past 6 years. So we assure you to provide very high quality (yet very simple) solutions which will fetch you maximum grade for sure. Email your assignment to info@assignmentpedia.com or info@programmingassignmentexperts.com. Mr. Neil shall go through your assignment and thereafter we shall provide you with a price quote. We just take a couple of minutes to reply to emails.
For more topics on programming in different technologies, platforms and languages, do have a look at our niche website viz: https://www.programmingassignmentexperts.com/
The detailed list of topics on Algorithm and Data Structures are on which we provide Help with Homework Assignments and Online Tutoring are listed under related topics. Some of the simple data structures on which we get frequent assignments are listed below:
Lists
External interface
- Create (list L)
- Insert (listtype item, position p, list L)
- Delete (position p, list L)
- position Lookup (listtype item, list L)
- listtype Retrieve (position p, list L)
- position First (list L)
- position Next (position p, list L)
- position Prev (position p, list L)
Implementations
- Store the list elements in an array, and represent positions using integer indices.
- Prev is O(1)
- Insert and Delete are O(N)
- Arrays are usually fixed in size
- Use a linked list of records containing an item of type listtype, and a pointer to the next record in the list. Represent positions as pointers to the appropriate record.
- Insert and Delete are O(N) unless position p is pointer to record containing position p-1
- Prev is O(N)
- Requires space for pointers
- Use a doubly-linked list of records, with pointers to the previous and next records in the list. Represent positions as above.
- Prev, Insert, and Delete are O(1)
- Requires twice as much space for pointers as previous implementation
Stacks
External interface
- Create (stack S)
- stacktype Top (stack S)
- stacktype Pop (stack S)
- Push (stacktype item, stack S)
- boolean Empty (stack S)
Implementations
Stacks are a limited form of lists (where all insert and delete operations take place at one end, called the top of the stack), so all implementations for lists apply.
- Implement stack in terms of list operations.
- Avoid O(N) Insert operations in array implementation!
- Use array implementation, with top of stack at the end of the array, and the stack grows downward.
- Push and Pop are O(1)
- Limits maximum size of stack
FIFO Queues
External interface
- Create (queue Q)
- queuetype Front (queue Q)
- Enqueue (queuetype item, queue Q)
- queuetype Dequeue (queue Q)
- boolean Empty (queue Q)
Implementations
Queues are also a limited form of list (where all inserts take place on at end, called the front, and all delete operations take place at the other end, called the rear), so all implementations for lists apply.
- Implement queue in terms of list operations.
- Use circular array implementation, with front and rear pointers (indices).
Trees
External Interface
- tree CreateEmptyTree ()
// Create an empty tree - tree CreateTreeN (labeltype label, tree T1 ... TN)
// Create a tree with root label and N children T1..TN - AddRightSubtree (tree subtree, node n)
// Make subtree the rightmost child of n - AddLeftSubtree (tree subtree, node n)
// Make subtree the leftmost child of n - node Root (tree T)
// Return the root node of T - node Parent (node n)
// Return the parent node of n - node LeftmostChild (node n)
// Return the leftmost child node of n - node RightSibling (node n)
// Return the right sibling of n - labeltype Label (node n)
// Return the label at node n
Implementations
When implementing general trees, we are constrained by the fact that each node may have an arbitrary number of children.
- Array representation: each tree is an array of node records, where each node contains the index of its parent in the array. Index 0 is used to refer to the empty tree.
- Parent is O(1); moving up the tree from leaf node to root requires time proportional to the height of the tree.
- Adding subtrees to an existing tree requires copying the tree from one array to another, since trees don't share array space.
- LeftmostChild and RightSibling are not well defined.
- Arrary with list of siblings representation: each tree is an array of parent nodes, each of which include a list of its children.
- LeftmostChild and RightSibling are O(1).
- Parent is O(N), where the tree has N nodes, since we have to search all the lists of childen to find a parent node.
- As before, trees don't share array space.
- Array of nodes, each of which holds the index of its leftmost child, right sibling, and parent. Every node in every tree is represented by an index into the one array of nodes.
- LeftmostChild, RightSibling, and Parent are O(1).
- All trees share array space.
- Same as above, using dynamic allocation for nodes, and pointers (rather than an index) to represent each node.
Binary Trees
External Interface
- tree CreateEmptyTree ()
// Create an empty binary tree - tree CreateTree (labeltype label, tree T1, tree T2)
// Create tree with root label, left child T1, right child T2 - MakeLeftChild (tree child, tree T)
// Make child the left subtree of T - MakeRightChild (tree child, tree T)
// Make child the right subtree of T - tree LeftChild (tree T)
// Return the left subtree of T - tree RightChild (tree T)
// Return the right subtree of T - labeltype Label (tree T)
// Return the label at root of T
Implementations
- Array of nodes, each of which holds the index of its left and right child.
- Same as above, using dynamic allocation for nodes, and pointers (rather than an index) to represent each node.
Sets
External interface
- Create (set S)
- Insert (elementtype item, set S)
- Delete (elementtype item, set S)
- boolean Member (elementtype item, set S)
- set Union (set S1, set S2)
- set Intersection (set S1, set s2)
- set Difference (set S1, set S2)
Implementations
- Bit vector
- Requires that elements be mapped to range 1..Max.
- Member, Insert, and Delete are O(1).
- Union, Intersection, and Difference are O(Max).
- Space overhead is O(Max) not O(|S|)
- Sorted linked list
- Can handle arbitrary element types
- Member, Insert, and Delete are O(|S|)
- Union, Intersection, and Difference are O(|S1|+|S2|)
- Space overhead is O(|S|)
- Open hash table (supporting dictionary operations Member, Insert, Delete)
- Member, Insert, and Delete are O(1) on average
- Requires a good hash function
Priority Queues
External interface
- Create (pqueue Q)
- Insert (elementtype item, pqueue Q)
- elementtype DeleteMin (pqueue Q)
Implementations
- Unsorted linked list
- Insert is O(1); DeleteMin is O(N)
- Sorted linked list
- DeleteMin is O(1); Insert is O(N)
- Partially ordered, balanced binary tree, where the value of a node is no greater than the value of its children (hence the minimum value is at the root). To maintain balance after deleting the root, move the rightmost leafnode to the root, and percolate it downwards based on its value. To insert, put new node at leftmost position in lowest level, and percolate upwards based on its value.
- DeleteMin and Insert are O(log N) since the height of a balanced binary tree of N nodes is log N.