#The stack class that I implemented

class LinkedList:
    """Implementation of a singly-linked List"""
    
    #-----------------This is a nested class------------------------
    class _Node:
        """Lightweight non-public class for storing nodes"""
    
        # __slots__ is a tuple that defines the dictionary entries
        __slots__ = ("_element", "_next")
    
    
        def __init__(self, element, next):
            """Constructor of a node object"""
            self._element = element
            self._next = next
    #-----------------This is a nested class------------------------
    
    
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0
        
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size==0
    
    def first(self):
        """Returns the first element in the Queue"""
        if self.is_empty():
            raise Empty("Queue is Empty")
            
        return self._head._element

    def last(self):
        """Returns the first element in the Queue"""
        if self.is_empty():
            raise Empty("Queue is Empty")
            
        return self._tail._element

    def add_first(self,e):
        """Adds an element to the front of the List"""
        
        # Create a new node with element e
        New_Node = self._Node(e,None)

        # if the list is empty, the head is the tail
        if self.is_empty():
            self._tail = New_Node
        else:
            # Update the link for the new head node to the old head
            New_Node._next = self._head
        # add node to the head = front
        self._head = New_Node
        # increase the size
        self._size  = 1
        
    def add_last(self,e):
        """Adds an element to the back of the List"""
        
        # Create a new node
        New_Node = self._Node(e,None)
        
        # if empty it goes as the head=tail
        if self.is_empty():
            self._head = New_Node
        # Normally enqueue to the tail = back of the queue
        else:
            # Update the link to the new tail node
            self._tail._next = New_Node
        # Enqueue'd elements go to the tail = back
        self._tail = New_Node
        # increase the size
        self._size  = 1

    def remove_first(self):
        """Remove an element from the front of the Queue"""
        
        if self.is_empty():
            raise Empty("List is Empty")

        # Grab output element
        output = self._head._element
        
        # re-assign the head of the linked-list
        self._head = self._head._next
        # update the size
        self._size -= 1
        # Check if that was the only element
        if self.is_empty():
            self._tail = None
        return output

So I am thinking of using a for loop in order to take the last element of the list and put it in front of the list and do it for the other elements until the linked list is reversed.

OK in my new code below I tried to take the last element and put it in the front but I am receiving None when I run the code.

# Create a linked list
L = LinkedList()

# Add element a to the front of the list
L.add_first(1)

print(L.first())
L.add_last(2)
L.add_last(3)
L.add_last(4)
L.add_last(5)

print("first = ",L.first())

print("last = ",L.last())

def reverseLinked():

    for i in range(len(L)):

        S.add_first(L.last())

    printL(S)

CodePudding user response：

If your list is

A -> B -> C

Where each node holds a reference to the next node, then to reverse it you would just start from the head, get the next node, have the next point to where you came from, and repeat until there is no more next node.

Eg:

• Start at A (prev node = None)
• Get next node (B)
• Set next node to prev node (None)
• Go to B
• Get next node (C)
• Set next node to prev node (B)

Then terminate when next node is None.

Since the question is to "describe an algorithm" I don't feel that working copy-pasteable code is necessary.

CodePudding user response：

This might not be the most efficient, but what you can do is make a new list that is empty. Move through your singly linked list and append each node to the list, then simply reverse the list.