Complete the implementation of the link-based set defined in the new class named LinkedSet that implements a set type using linked nodes. Hint: Much of the code in the LinkedBag class from your solution of the linkedbag.py file in Programming Exercise 5.5 can be reused. In the linkedset.py file, complete the following: Complete the accessor methods: isEmpty(), returns true if len(self) == 0, or false otherwise. __len__, returns the number of items in self. __str__, returns the string representation of self. __iter__, supports iteration over a view of self. __add__, returns anew set containing the contents of self and other clone, return a copy of self. __eq__, returns true if self equals other, or false otherwise count, return the numer of instance of item in self. Complete the mutator methods: clear, makes self become empty. add, adds item to self and ignores the item if it’s already in the set. Check array memory and increase it if necessary remove, removes item from self if it's in self. Check precondition and raise KeyError if necessary Search for the node containing the target item, probe will point to the target node, and trailer will point to the one before it, if it exists. Unhook the node to be deleted, either the first one or one thereafter. Decrement logical size To test your program run the test method in the testset.py file. from node import Node class LinkedSet(object): """A link-based set implementation."""
Types of Linked List
A sequence of data elements connected through links is called a linked list (LL). The elements of a linked list are nodes containing data and a reference to the next node in the list. In a linked list, the elements are stored in a non-contiguous manner and the linear order in maintained by means of a pointer associated with each node in the list which is used to point to the subsequent node in the list.
Linked List
When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).
Complete the implementation of the link-based set defined in the new class named LinkedSet that implements a set type using linked nodes.
Hint: Much of the code in the LinkedBag class from your solution of the linkedbag.py file in Programming Exercise 5.5 can be reused.
In the linkedset.py file, complete the following:
- Complete the accessor methods:
- isEmpty(), returns true if len(self) == 0, or false otherwise.
- __len__, returns the number of items in self.
- __str__, returns the string representation of self.
- __iter__, supports iteration over a view of self.
- __add__, returns anew set containing the contents of self and other
- clone, return a copy of self.
- __eq__, returns true if self equals other, or false otherwise
- count, return the numer of instance of item in self.
- Complete the mutator methods:
- clear, makes self become empty.
- add, adds item to self and ignores the item if it’s already in the set.
- Check array memory and increase it if necessary
- remove, removes item from self if it's in self.
- Check precondition and raise KeyError if necessary
- Search for the node containing the target item, probe will point to the target node, and trailer will point to the one before it, if it exists.
- Unhook the node to be deleted, either the first one or one thereafter.
- Decrement logical size
To test your program run the test method in the testset.py file.
from node import Node
class LinkedSet(object):
"""A link-based set implementation."""
# Constructor
def __init__(self, sourceCollection = None):
"""Sets the initial state of self, which includes the
contents of sourceCollection, if it's present."""
# Accessor methods
def isEmpty(self):
"""Returns True if len(self) == 0, or False otherwise."""
def __len__(self):
"""-Returns the number of items in self."""
def __str__(self):
"""Returns the string representation of self."""
def __iter__(self):
"""Supports iteration over a view of self."""
def __add__(self, other):
"""Returns a new set containing the contents
of self and other."""
def clone(self):
"""Returns a copy of self."""
def __eq__(self, other):
"""Returns True if self equals other,
or False otherwise."""
# Mutator methods
def clear(self):
"""Makes self become empty."""
def add(self, item):
"""Adds item to self."""
def remove(self, item):
"""Precondition: item is in self.
Raises: KeyError if item in not in self.
Postcondition: item is removed from self."""
# Check precondition and raise if necessary
# Search for the node containing the target item
# probe will point to the target node, and trailer
# will point to the one before it, if it exists
# Unhook the node to be deleted, either the first one or one
# thereafter
# Decrement logical size
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 4 images
