Click here to Skip to main content
15,901,368 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
Write a class LinkedList that holds a linked list of values. Your class should be in a source file named linked_list.py, and should support the following operations:

LinkedList(list) - create a LinkedList that initially holds the values in the given Python list

l.to_list() - return a Python list containing the values in this LinkedList

l.len() - return the number of nodes in a LinkedList

l.get(n) - return the value in the nth node, where nodes are numbered from 0. You may assume that 0 <= n < l.len().

l.has(x) - true if the list includes the value x

l.delete(x) - delete the first occurrence (if any) of the value x

l.rotate() - move the last node in the list to the head of the list; does nothing if the list is empty

l.starts_with(m) - true if the elements of the LinkedList m appear at the beginning of l

l.contains(m) - true if the elements of the LinkedList m appear in succession anywhere in l

l.ends_with(m) - true if the elements of the LinkedList m appear in succession at the end of l

Important: You may not use Python lists anywhere, except in the initializer and the to_list() method. Your LinkedList class may not store a Python list in any attribute. Also, generators (which we will study later in Programming 1) are not allowed in this assignment.

You do not need to read any input or write any output; simply submit a file linked_list.py containing the class described above.

Sample usage #1:

>>> l = LinkedList([2, 7, 4, 9, 18, 19, 22])
>>> l.to_list()
[2, 7, 4, 9, 18, 19, 22]
>>> l.len()
7
>>> l.get(3)
9
>>> l.has(17)
False
>>> o = LinkedList([7])
>>> o.to_list()
[7]
>>> o.len()
1
>>> e = LinkedList([])
>>> e.to_list()
[]
>>> e.len()
0
Sample usage #2:

>>> l = LinkedList([2, 7, 6, 4])
>>> l.delete(2)
>>> l.delete(5)
>>> l.delete(4)
>>> l.to_list()
[7, 6]
>>> l.delete(6)
>>> l.delete(7)
>>> l.to_list()
[]
>>> l.delete(8)
>>> l.to_list()
[]


What I have tried:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self, values):
        self.head = None
        self.length = 0  # Track the length of the linked list
        for value in values:
            self.append(value)

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.length += 1

    def to_list(self):
        result = []
        current = self.head
        while current:
            result.append(current.value)
            current = current.next
        return result

    def len(self):
        return self.length

    def get(self, n):
        if n < 0 or n >= self.length:
            raise IndexError("Index out of range")
        current = self.head
        for _ in range(n):
            current = current.next
        return current.value

    def has(self, x):
        current = self.head
        while current:
            if current.value == x:
                return True
            current = current.next
        return False

    def delete(self, x):
        if not self.head:
            return
        if self.head.value == x:
            self.head = self.head.next
            self.length -= 1
            return
        current = self.head
        while current.next:
            if current.next.value == x:
                current.next = current.next.next
                self.length -= 1
                return
            current = current.next

    def rotate(self):
        if not self.head or not self.head.next:
            return
        current = self.head
        while current.next.next:
            current = current.next
        current.next.next = self.head
        self.head = current.next
        current.next = None

    def starts_with(self, m):
        current_l = self.head
        current_m = m.head
        while current_l and current_m:
            if current_l.value != current_m.value:
                return False
            current_l = current_l.next
            current_m = current_m.next
        return not current_m

    def contains(self, m):
        current_l = self.head
        while current_l:
            if self.starts_with_helper(current_l, m):
                return True
            current_l = current_l.next
        return False

    def starts_with_helper(self, l, m):
        current_l = l
        current_m = m.head
        while current_l and current_m:
            if current_l.value != current_m.value:
                return False
            current_l = current_l.next
            current_m = current_m.next
        return not current_m

    def ends_with(self, m):
        current_l = self.head
        current_m = m.head
        if not current_m:
            return True
        while current_l.next:
            current_l = current_l.next
        while current_m.next:
            current_m = current_m.next
        while current_l and current_m:
            if current_l.value != current_m.value:
                return False
            current_l = current_l.next
            current_m = current_m.next
        return not current_m
Posted
Comments
Mike Hankey 19-Feb-24 18:19pm    
Is there a question?

What are you having problems with?
SAM SAMI 2024 19-Feb-24 23:26pm    
What does the teacher mean about this part when he said: (You may not use Python lists anywhere, except in the initializer and the to_list() method. Your LinkedList class may not store a Python list in any attribute. Also, generators are not allowed in this assignment. )?
Should we bring the mentioned samples (Sample usage 1 & 2) into the program code or should we enter them in the CMD field?

1 solution

Quote:
You may not use Python lists anywhere, except in the initializer and the to_list() method. Your LinkedList class may not store a Python list in any attribute. Also, generators are not allowed in this assignment.

It's pretty clear: you cannot use a List except where he specifically allowed it. This is to ensure that you are genuinely creating and traversing links instead of storing them in a Python collection and using it's inbuilt access methods.
Generators you have not studied yet - they are coming later - so if "your" code includes them because you copy'n'paste an example from the internet you will fail the exercise. So if you do plagiarise (which is a really bad idea anyway) you will need to understand the code you steal in very good detail before you submit it. It'll be a lot easier to write your own code anyway because then you can't use elements you haven't met yet!
 
Share this answer
 
Comments
CPallini 20-Feb-24 2:05am    
5.
Maciej Los 20-Feb-24 16:06pm    
5ed!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900