Неизменяемые списки лучше всего представлены в виде двух кортежей, где None представляет NIL. Чтобы упростить составление таких списков, вы можете использовать эту функцию:

def mklist(*args):
    result = None
    for element in reversed(args):
        result = (element, result)
    return result

Для работы с такими списками я бы предпочел предоставить всю коллекцию функций LISP (т.е. first, second, nth и т.д.), чем вводить методы.

Я написал это на днях

#! /usr/bin/env python

class Node(object):
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node


class LinkedList:
    def __init__(self):
        self.cur_node = None

    def add_node(self, data):
        new_node = Node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node #  set the current node to the new one.

    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print node.data
            node = node.next



ll = LinkedList()
ll.add_node(1)
ll.add_node(2)
ll.add_node(3)

ll.list_print()

При использовании неизменяемых связанных списков рассмотрите возможность прямого использования кортежа Python.

ls = (1, 2, 3, 4, 5)

def first(ls): return ls[0]
def rest(ls): return ls[1:]

Это действительно такая простота, и вы можете сохранить дополнительные функции, такие как len (ls), x в ls и т. д.

Вот немного более сложная версия класса связанного списка с интерфейсом, аналогичным типам последовательностей Python (т.е. поддерживает индексацию, нарезку, конкатенацию с произвольными последовательностями и т. д.). Он должен иметь начало O (1), не копирует данные, если в этом нет необходимости, и может использоваться взаимозаменяемо с кортежами.

Это не будет так эффективно по пространству или времени, как ячейки cons-lisp, поскольку классы python, очевидно, немного тяжелее (вы можете немного улучшить ситуацию с помощью "__slots__ = '_head','_tail'", чтобы уменьшить использование памяти). Однако он будет иметь желаемые рабочие характеристики большого O.

Пример использования:

>>> l = LinkedList([1,2,3,4])
>>> l
LinkedList([1, 2, 3, 4])
>>> l.head, l.tail
(1, LinkedList([2, 3, 4]))

# Prepending is O(1) and can be done with:
LinkedList.cons(0, l)
LinkedList([0, 1, 2, 3, 4])
# Or prepending arbitrary sequences (Still no copy of l performed):
[-1,0] + l
LinkedList([-1, 0, 1, 2, 3, 4])

# Normal list indexing and slice operations can be performed.
# Again, no copy is made unless needed.
>>> l[1], l[-1], l[2:]
(2, 4, LinkedList([3, 4]))
>>> assert l[2:] is l.next.next

# For cases where the slice stops before the end, or uses a
# non-contiguous range, we do need to create a copy.  However
# this should be transparent to the user.
>>> LinkedList(range(100))[-10::2]
LinkedList([90, 92, 94, 96, 98])

Выполнение:

import itertools

class LinkedList(object):
    """Immutable linked list class."""

    def __new__(cls, l=[]):
        if isinstance(l, LinkedList): return l # Immutable, so no copy needed.
        i = iter(l)
        try:
            head = i.next()
        except StopIteration:
            return cls.EmptyList   # Return empty list singleton.

        tail = LinkedList(i)

        obj = super(LinkedList, cls).__new__(cls)
        obj._head = head
        obj._tail = tail
        return obj

    @classmethod
    def cons(cls, head, tail):
        ll =  cls([head])
        if not isinstance(tail, cls):
            tail = cls(tail)
        ll._tail = tail
        return ll

    # head and tail are not modifiable
    @property  
    def head(self): return self._head

    @property
    def tail(self): return self._tail

    def __nonzero__(self): return True

    def __len__(self):
        return sum(1 for _ in self)

    def __add__(self, other):
        other = LinkedList(other)

        if not self: return other   # () + l = l
        start=l = LinkedList(iter(self))  # Create copy, as we'll mutate

        while l:
            if not l._tail: # Last element?
                l._tail = other
                break
            l = l._tail
        return start

    def __radd__(self, other):
        return LinkedList(other) + self

    def __iter__(self):
        x=self
        while x:
            yield x.head
            x=x.tail

    def __getitem__(self, idx):
        """Get item at specified index"""
        if isinstance(idx, slice):
            # Special case: Avoid constructing a new list, or performing O(n) length 
            # calculation for slices like l[3:].  Since we're immutable, just return
            # the appropriate node. This becomes O(start) rather than O(n).
            # We can't do this for  more complicated slices however (eg [l:4]
            start = idx.start or 0
            if (start >= 0) and (idx.stop is None) and (idx.step is None or idx.step == 1):
                no_copy_needed=True
            else:
                length = len(self)  # Need to calc length.
                start, stop, step = idx.indices(length)
                no_copy_needed = (stop == length) and (step == 1)

            if no_copy_needed:
                l = self
                for i in range(start): 
                    if not l: break # End of list.
                    l=l.tail
                return l
            else:
                # We need to construct a new list.
                if step < 1:  # Need to instantiate list to deal with -ve step
                    return LinkedList(list(self)[start:stop:step])
                else:
                    return LinkedList(itertools.islice(iter(self), start, stop, step))
        else:       
            # Non-slice index.
            if idx < 0: idx = len(self)+idx
            if not self: raise IndexError("list index out of range")
            if idx == 0: return self.head
            return self.tail[idx-1]

    def __mul__(self, n):
        if n <= 0: return Nil
        l=self
        for i in range(n-1): l += self
        return l
    def __rmul__(self, n): return self * n

    # Ideally we should compute the has ourselves rather than construct
    # a temporary tuple as below.  I haven't impemented this here
    def __hash__(self): return hash(tuple(self))

    def __eq__(self, other): return self._cmp(other) == 0
    def __ne__(self, other): return not self == other
    def __lt__(self, other): return self._cmp(other) < 0
    def __gt__(self, other): return self._cmp(other) > 0
    def __le__(self, other): return self._cmp(other) <= 0
    def __ge__(self, other): return self._cmp(other) >= 0

    def _cmp(self, other):
        """Acts as cmp(): -1 for self<other, 0 for equal, 1 for greater"""
        if not isinstance(other, LinkedList):
            return cmp(LinkedList,type(other))  # Arbitrary ordering.

        A, B = iter(self), iter(other)
        for a,b in itertools.izip(A,B):
           if a<b: return -1
           elif a > b: return 1

        try:
            A.next()
            return 1  # a has more items.
        except StopIteration: pass

        try:
            B.next()
            return -1  # b has more items.
        except StopIteration: pass

        return 0  # Lists are equal

    def __repr__(self):
        return "LinkedList([%s])" % ', '.join(map(repr,self))

class EmptyList(LinkedList):
    """A singleton representing an empty list."""
    def __new__(cls):
        return object.__new__(cls)

    def __iter__(self): return iter([])
    def __nonzero__(self): return False

    @property
    def head(self): raise IndexError("End of list")

    @property
    def tail(self): raise IndexError("End of list")

# Create EmptyList singleton
LinkedList.EmptyList = EmptyList()
del EmptyList

Для некоторых нужд также может быть полезен дек. Вы можете добавлять и удалять предметы на обоих концах двухсторонней очереди по цене O (1).

from collections import deque
d = deque([1,2,3,4])

print d
for x in d:
    print x
print d.pop(), d

Вот несколько функций списка, основанных на Представительство Мартина против Лёвиса:

cons   = lambda el, lst: (el, lst)
mklist = lambda *args: reduce(lambda lst, el: cons(el, lst), reversed(args), None)
car = lambda lst: lst[0] if lst else lst
cdr = lambda lst: lst[1] if lst else lst
nth = lambda n, lst: nth(n-1, cdr(lst)) if n > 0 else car(lst)
length  = lambda lst, count=0: length(cdr(lst), count+1) if lst else count
begin   = lambda *args: args[-1]
display = lambda lst: begin(w("%s " % car(lst)), display(cdr(lst))) if lst else w("nil\n")

где w = sys.stdout.write

Хотя двусвязные списки широко используются в рецепт заказанного набора Раймонда Хеттингера, односвязные списки не имеют практического значения в Python.

Я никогда использовал односвязный список в Python для любых задач, кроме образовательных.

Томас Уотнедал предложенный хороший образовательный ресурс Как думать как компьютерный ученый, Глава 17: Связанные списки:

Связанный список:

• пустой список, представленный None, или

• узел, содержащий грузовой объект и ссылку на связанный список.

  class Node: 
    def __init__(self, cargo=None, next=None): 
      self.car = cargo 
      self.cdr = next    
    def __str__(self): 
      return str(self.car)
  
  def display(lst):
    if lst:
      w("%s " % lst)
      display(lst.cdr)
    else:
      w("nil\n")
  

Принятый ответ довольно сложен. Вот более стандартный дизайн:

L = LinkedList()
L.insert(1)
L.insert(1)
L.insert(2)
L.insert(4)
print L
L.clear()
print L

Это простой класс LinkedList, основанный на простом дизайне C++ и Глава 17: Связанные списки, как рекомендовано Томас Уотнедал.

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

    def __str__(self):
        return 'Node ['+str(self.value)+']'

class LinkedList:
    def __init__(self):
        self.first = None
        self.last = None

    def insert(self, x):
        if self.first == None:
            self.first = Node(x, None)
            self.last = self.first
        elif self.last == self.first:
            self.last = Node(x, None)
            self.first.next = self.last
        else:
            current = Node(x, None)
            self.last.next = current
            self.last = current

    def __str__(self):
        if self.first != None:
            current = self.first
            out = 'LinkedList [\n' +str(current.value) +'\n'
            while current.next != None:
                current = current.next
                out += str(current.value) + '\n'
            return out + ']'
        return 'LinkedList []'

    def clear(self):
        self.__init__()

Я основал эту дополнительную функцию на Ник Стинейтс

def add_node_at_end(self, data):
    new_node = Node()
    node = self.curr_node
    while node:
        if node.next == None:
            node.next = new_node
            new_node.next = None
            new_node.data = data
        node = node.next

Метод, который он использует, добавляет новый узел в начале, в то время как я видел много реализаций, которые обычно добавляют новый узел в конце, но в любом случае это весело.

Я думаю, что приведенная ниже реализация вполне изящно восполняет счет.

'''singly linked lists, by Yingjie Lan, December 1st, 2011'''

class linkst:
    '''Singly linked list, with pythonic features.
The list has pointers to both the first and the last node.'''
    __slots__ = ['data', 'next'] #memory efficient
    def __init__(self, iterable=(), data=None, next=None):
        '''Provide an iterable to make a singly linked list.
Set iterable to None to make a data node for internal use.'''
        if iterable is not None: 
            self.data, self.next = self, None
            self.extend(iterable)
        else: #a common node
            self.data, self.next = data, next

    def empty(self):
        '''test if the list is empty'''
        return self.next is None

    def append(self, data):
        '''append to the end of list.'''
        last = self.data
        self.data = last.next = linkst(None, data)
        #self.data = last.next

    def insert(self, data, index=0):
        '''insert data before index.
Raise IndexError if index is out of range'''
        curr, cat = self, 0
        while cat < index and curr:
            curr, cat = curr.next, cat+1
        if index<0 or not curr:
            raise IndexError(index)
        new = linkst(None, data, curr.next)
        if curr.next is None: self.data = new
        curr.next = new

    def reverse(self):
        '''reverse the order of list in place'''
        current, prev = self.next, None
        while current: #what if list is empty?
            next = current.next
            current.next = prev
            prev, current = current, next
        if self.next: self.data = self.next
        self.next = prev

    def delete(self, index=0):
        '''remvoe the item at index from the list'''
        curr, cat = self, 0
        while cat < index and curr.next:
            curr, cat = curr.next, cat+1
        if index<0 or not curr.next:
            raise IndexError(index)
        curr.next = curr.next.next
        if curr.next is None: #tail
            self.data = curr #current == self?

    def remove(self, data):
        '''remove first occurrence of data.
Raises ValueError if the data is not present.'''
        current = self
        while current.next: #node to be examined
            if data == current.next.data: break
            current = current.next #move on
        else: raise ValueError(data)
        current.next = current.next.next
        if current.next is None: #tail
            self.data = current #current == self?

    def __contains__(self, data):
        '''membership test using keyword 'in'.'''
        current = self.next
        while current:
            if data == current.data:
                return True
            current = current.next
        return False

    def __iter__(self):
        '''iterate through list by for-statements.
return an iterator that must define the __next__ method.'''
        itr = linkst()
        itr.next = self.next
        return itr #invariance: itr.data == itr

    def __next__(self):
        '''the for-statement depends on this method
to provide items one by one in the list.
return the next data, and move on.'''
        #the invariance is checked so that a linked list
        #will not be mistakenly iterated over
        if self.data is not self or self.next is None:
            raise StopIteration()
        next = self.next
        self.next = next.next
        return next.data

    def __repr__(self):
        '''string representation of the list'''
        return 'linkst(%r)'%list(self)

    def __str__(self):
        '''converting the list to a string'''
        return '->'.join(str(i) for i in self)

    #note: this is NOT the class lab! see file linked.py.
    def extend(self, iterable):
        '''takes an iterable, and append all items in the iterable
to the end of the list self.'''
        last = self.data
        for i in iterable:
            last.next = linkst(None, i)
            last = last.next
        self.data = last

    def index(self, data):
        '''TODO: return first index of data in the list self.
    Raises ValueError if the value is not present.'''
        #must not convert self to a tuple or any other containers
        current, idx = self.next, 0
        while current:
            if current.data == data: return idx
            current, idx = current.next, idx+1
        raise ValueError(data)

Вот что я придумал. Это аналог Риккардо К. в этом потоке, за исключением того, что он печатает числа по порядку, а не в обратном порядке. Я также сделал объект LinkedList итератором Python, чтобы распечатать список, как обычный список Python.

class Node:

    def __init__(self, data=None):
        self.data = data
        self.next = None

    def __str__(self):
        return str(self.data)


class LinkedList:

    def __init__(self):
        self.head = None
        self.curr = None
        self.tail = None

    def __iter__(self):
        return self

    def next(self):
        if self.head and not self.curr:
            self.curr = self.head
            return self.curr
        elif self.curr.next:
            self.curr = self.curr.next
            return self.curr
        else:
            raise StopIteration

    def append(self, data):
        n = Node(data)
        if not self.head:
            self.head = n
            self.tail = n
        else:
            self.tail.next = n
            self.tail = self.tail.next


# Add 5 nodes
ll = LinkedList()
for i in range(1, 6):
    ll.append(i)

# print out the list
for n in ll:
    print n

"""
Example output:
$ python linked_list.py
1
2
3
4
5
"""

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

    def insert(self, node):
        if not self.next:
            self.next = node
        else:
            self.next.insert(node)

    def __str__(self):
        if self.next:
            return '%s -> %s' % (self.value, str(self.next))
        else:
            return ' %s ' % self.value

if __name__ == "__main__":
    items = ['a', 'b', 'c', 'd', 'e']    
    ll = None
    for item in items:
        if ll:
            next_ll = LinkedList(item)
            ll.insert(next_ll)
        else:
            ll = LinkedList(item)
    print('[ %s ]' % ll)

Я просто сделал это как забавную игрушку. Он должен быть неизменным, если вы не касаетесь методов с префиксом подчеркивания, и он реализует кучу магии Python, такую ​​как индексирование и len.

Прежде всего, я предполагаю, что вам нужны связанные списки. На практике вы можете использовать collections.deque, чья текущая реализация CPython представляет собой двусвязный список блоков (каждый блок содержит массив из 62 грузовых объектов). Он включает в себя функции связанного списка. Вы также можете найти расширение C под названием llist на pypi. Если вам нужна простая и понятная реализация ADT связанного списка на чистом Python, вы можете взглянуть на мою следующую минимальную реализацию.

class Node (object):
    """ Node for a linked list. """
    def __init__ (self, value, next=None):
        self.value = value
        self.next = next

class LinkedList (object):
    """ Linked list ADT implementation using class. 
        A linked list is a wrapper of a head pointer
        that references either None, or a node that contains 
        a reference to a linked list.
    """
    def __init__ (self, iterable=()):
        self.head = None
        for x in iterable:
            self.head = Node(x, self.head)

    def __iter__ (self):
        p = self.head
        while p is not None:
            yield p.value
            p = p.next

    def prepend (self, x):  # 'appendleft'
        self.head = Node(x, self.head)

    def reverse (self):
        """ In-place reversal. """
        p = self.head
        self.head = None
        while p is not None:
            p0, p = p, p.next
            p0.next = self.head
            self.head = p0

if __name__ == '__main__':
    ll = LinkedList([6,5,4])
    ll.prepend(3); ll.prepend(2)
    print list(ll)
    ll.reverse()
    print list(ll)

class LL(object):
    def __init__(self,val):
        self.val = val
        self.next = None

    def pushNodeEnd(self,top,val):
        if top is None:
            top.val=val
            top.next=None
        else:
            tmp=top
            while (tmp.next != None):
                tmp=tmp.next        
            newNode=LL(val)
            newNode.next=None
            tmp.next=newNode

    def pushNodeFront(self,top,val):
        if top is None:
            top.val=val
            top.next=None
        else:
            newNode=LL(val)
            newNode.next=top
            top=newNode

    def popNodeFront(self,top):
        if top is None:
            return
        else:
            sav=top
            top=top.next
        return sav

    def popNodeEnd(self,top):
        if top is None:
            return
        else:
            tmp=top
            while (tmp.next != None):
                prev=tmp
                tmp=tmp.next
            prev.next=None
        return tmp

top=LL(10)
top.pushNodeEnd(top, 20)
top.pushNodeEnd(top, 30)
pop=top.popNodeEnd(top)
print (pop.val)

Я поместил класс односвязного списка Python 2.x и 3.x в https://pypi.python.org/pypi/linked_list_mod/

Он протестирован с CPython 2.7, CPython 3.4, Pypy 2.3.1, Pypy3 2.3.1 и Jython 2.7b2 и поставляется с хорошим автоматическим набором тестов.

Он также включает классы LIFO и FIFO.

Однако они не неизменны.

Мои 2 цента

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

    def __str__(self):
        return str(self.value)


class LinkedList:
    def __init__(self):
        self.first = None
        self.last = None

    def add(self, x):
        current = Node(x, None)
        try:
            self.last.next = current
        except AttributeError:
            self.first = current
            self.last = current
        else:
            self.last = current

    def print_list(self):
        node = self.first
        while node:
            print node.value
            node = node.next

ll = LinkedList()
ll.add("1st")
ll.add("2nd")
ll.add("3rd")
ll.add("4th")
ll.add("5th")

ll.print_list()

# Result: 
# 1st
# 2nd
# 3rd
# 4th
# 5th

enter code here
enter code here

class node:
    def __init__(self):
        self.data = None
        self.next = None
class linked_list:
    def __init__(self):
        self.cur_node = None
        self.head = None
    def add_node(self,data):
        new_node = node()
        if self.head == None:
            self.head = new_node
            self.cur_node = new_node
        new_node.data = data
        new_node.next = None
        self.cur_node.next = new_node
        self.cur_node = new_node
    def list_print(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    def delete(self):
        node = self.head
        next_node = node.next
        del(node)
        self.head = next_node
a = linked_list()
a.add_node(1)
a.add_node(2)
a.add_node(3)
a.add_node(4)
a.delete()
a.list_print()

Если вы хотите просто создать простой список понравившихся, обратитесь к этому коду

l = [1, [2, [3, [4, [5], [6, [7, [8, [9, [10]]]]]]]]]]

для визуализации выполнения этой трески посетите http://www.pythontutor.com/visualize.html#mode=edit

class LinkedStack:
'''LIFO Stack implementation using a singly linked list for storage.'''

_ToList = []

#---------- nested _Node class -----------------------------
class _Node:
    '''Lightweight, nonpublic class for storing a singly linked node.'''
    __slots__ = '_element', '_next'     #streamline memory usage

    def __init__(self, element, next):
        self._element = element
        self._next = next

#--------------- stack methods ---------------------------------
def __init__(self):
    '''Create an empty stack.'''
    self._head = None
    self._size = 0

def __len__(self):
    '''Return the number of elements in the stack.'''
    return self._size

def IsEmpty(self):
    '''Return True if the stack is empty'''
    return  self._size == 0

def Push(self,e):
    '''Add element e to the top of the Stack.'''
    self._head = self._Node(e, self._head)      #create and link a new node
    self._size +=1
    self._ToList.append(e)

def Top(self):
    '''Return (but do not remove) the element at the top of the stack.
       Raise exception if the stack is empty
    '''

    if self.IsEmpty():
        raise Exception('Stack is empty')
    return  self._head._element             #top of stack is at head of list

def Pop(self):
    '''Remove and return the element from the top of the stack (i.e. LIFO).
       Raise exception if the stack is empty
    '''
    if self.IsEmpty():
        raise Exception('Stack is empty')
    answer = self._head._element
    self._head = self._head._next       #bypass the former top node
    self._size -=1
    self._ToList.remove(answer)
    return answer

def Count(self):
    '''Return how many nodes the stack has'''
    return self.__len__()

def Clear(self):
    '''Delete all nodes'''
    for i in range(self.Count()):
        self.Pop()

def ToList(self):
    return self._ToList

Класс связанного списка

class LinkedStack:
# Nested Node Class
class Node:
    def __init__(self, element, next):
        self.__element = element
        self.__next = next

    def get_next(self):
        return self.__next

    def get_element(self):
        return self.__element

def __init__(self):
    self.head = None
    self.size = 0
    self.data = []

def __len__(self):
    return self.size

def __str__(self):
    return str(self.data)

def is_empty(self):
    return self.size == 0

def push(self, e):
    newest = self.Node(e, self.head)
    self.head = newest
    self.size += 1
    self.data.append(newest)

def top(self):
    if self.is_empty():
        raise Empty('Stack is empty')
    return self.head.__element

def pop(self):
    if self.is_empty():
        raise Empty('Stack is empty')
    answer = self.head.element
    self.head = self.head.next
    self.size -= 1
    return answer

использование

from LinkedStack import LinkedStack

x = LinkedStack()

x.push(10)
x.push(25)
x.push(55)


for i in range(x.size - 1, -1, -1):

    print '|', x.data[i].get_element(), '|' ,
    #next object

    if x.data[i].get_next() == None:
        print '--> None'
    else:
        print  x.data[i].get_next().get_element(), '-|---->  ',

Выход

| 55 | 25 -|---->   | 25 | 10 -|---->   | 10 | --> None

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

    def setData(self, data):
        self.data = data
        return self.data

    def setNext(self, next):
        self.next = next

    def getNext(self):
        return self.next

    def hasNext(self):
        return self.next != None


class singleLinkList(object):

    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def insertAtBeginning(self, data):
        newNode = Node()
        newNode.setData(data)

        if self.listLength() == 0:
            self.head = newNode
        else:
            newNode.setNext(self.head)
            self.head = newNode

    def insertAtEnd(self, data):
        newNode = Node()
        newNode.setData(data)

        current = self.head

        while current.getNext() != None:
            current = current.getNext()

        current.setNext(newNode)

    def listLength(self):
        current = self.head
        count = 0

        while current != None:
            count += 1
            current = current.getNext()
        return count

    def print_llist(self):
        current = self.head
        print("List Start.")
        while current != None:
            print(current.getData())
            current = current.getNext()

        print("List End.")



if __name__ == '__main__':
    ll = singleLinkList()
    ll.insertAtBeginning(55)
    ll.insertAtEnd(56)
    ll.print_llist()
    print(ll.listLength())

Вот моя простая реализация:

class Node:
    def __init__(self):
        self.data = None
        self.next = None
    def __str__(self):
        return "Data %s: Next -> %s"%(self.data, self.next)

class LinkedList:
    def __init__(self):
        self.head = Node()
        self.curNode = self.head
    def insertNode(self, data):
        node = Node()
        node.data = data
        node.next = None
        if self.head.data == None:
            self.head = node
            self.curNode = node
        else:
            self.curNode.next = node
            self.curNode = node
    def printList(self):
        print self.head

l = LinkedList()
l.insertNode(1)
l.insertNode(2)
l.insertNode(34)

Выход:

Data 1: Next -> Data 2: Next -> Data 34: Next -> Data 4: Next -> None

llist - типы данных связанного списка для Python

Модуль llist реализует структуры данных связанных списков. Он поддерживает двусвязный список, то есть dllist, и односвязную структуру данных sllist.

dllist объекты

Этот объект представляет собой структуру данных двусвязного списка.

first

Первый объект dllistnode в списке. None, если список пуст.

last

Последний объект dllistnode в списке. Нет, если список пуст.

dllist объекты также поддерживают следующие методы:

append(x)

Добавьте x в правую часть списка и верните вставленный dllistnode.

appendleft(x)

Добавьте x в левую часть списка и верните вставленный dllistnode.

appendright(x)

Добавьте x в правую часть списка и верните вставленный dllistnode.

clear()

Удалите все узлы из списка.

extend(iterable)

Добавьте элементы из iterable в правую часть списка.

extendleft(iterable)

Добавьте элементы из iterable в левую часть списка.

extendright(iterable)

Добавьте элементы из iterable в правую часть списка.

insert(x[, before])

Добавьте x в правую часть списка, если before не указан, или вставьте x в левую часть dllistnode before. Вернуть вставленный dllistnode.

nodeat(index)

Узел возврата (типа dllistnode) в index.

pop()

Удалите и верните значение элемента из правой части списка.

popleft()

Удалите и верните значение элемента из левой части списка.

popright()

Удалить и вернуть значение элемента из правой части списка

remove(node)

Удалите node из списка и верните элемент, который был в нем сохранен.

dllistnode объекты

класс llist.dllistnode([value])

Вернуть новый узел двусвязного списка, инициализированный (необязательно) с помощью value.

Объекты dllistnode предоставляют следующие атрибуты:

next

Следующий узел в списке. Этот атрибут доступен только для чтения.

prev

Предыдущий узел в списке. Этот атрибут доступен только для чтения.

value

Значение, хранящееся в этом узле. Составлено по этой ссылке

продавец

класс llist.sllist([iterable]) Вернуть новый односвязный список, инициализированный элементами из iterable. Если итерабельность не указана, новый sllist пуст.

Аналогичный набор атрибутов и операций определен для этого объекта sllist. См. Эту ссылку для получения дополнительной информации.

Пример связанного списка вдвойне (сохранить как connectedlist.py):

class node:
    def __init__(self, before=None, cargo=None, next=None): 
        self._previous = before
        self._cargo = cargo 
        self._next  = next 

    def __str__(self):
        return str(self._cargo) or None 

class linkedList:
    def __init__(self): 
        self._head = None 
        self._length = 0

    def add(self, cargo):
        n = node(None, cargo, self._head)
        if self._head:
            self._head._previous = n
        self._head = n
        self._length += 1

    def search(self,cargo):
        node = self._head
        while (node and node._cargo != cargo):
            node = node._next
        return node

    def delete(self,cargo):
        node = self.search(cargo)
        if node:
            prev = node._previous
            nx = node._next
            if prev:
                prev._next = node._next
            else:
                self._head = nx
                nx._previous = None
            if nx:
                nx._previous = prev 
            else:
                prev._next = None
        self._length -= 1

    def __str__(self):
        print 'Size of linked list: ',self._length
        node = self._head
        while node:
            print node
            node = node._next

Тестирование (сохранить как test.py):

from linkedlist import node, linkedList

def test():

    print 'Testing Linked List'

    l = linkedList()

    l.add(10)
    l.add(20)
    l.add(30)
    l.add(40)
    l.add(50)
    l.add(60)

    print 'Linked List after insert nodes:'
    l.__str__()

    print 'Search some value, 30:'
    node = l.search(30)
    print node

    print 'Delete some value, 30:'
    node = l.delete(30)
    l.__str__()

    print 'Delete first element, 60:'
    node = l.delete(60)
    l.__str__()

    print 'Delete last element, 10:'
    node = l.delete(10)
    l.__str__()


if __name__ == "__main__":
    test()

Выход:

Testing Linked List
Linked List after insert nodes:
Size of linked list:  6
60
50
40
30
20
10
Search some value, 30:
30
Delete some value, 30:
Size of linked list:  5
60
50
40
20
10
Delete first element, 60:
Size of linked list:  4
50
40
20
10
Delete last element, 10:
Size of linked list:  3
50
40
20

Вот мое решение:

Выполнение

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

  def get_data(self):
    return self.data

  def set_data(self, data):
    self.data = data

  def get_next(self):
    return self.next

  def set_next(self, node):
    self.next = node


# ------------------------ Link List class ------------------------------- #
class LinkList:

  def __init__(self):
    self.head = None

  def is_empty(self):
    return self.head == None

  def traversal(self, data=None):
    node = self.head
    index = 0
    found = False
    while node is not None and not found:
      if node.get_data() == data:
        found = True
      else:
        node = node.get_next()
        index += 1
    return (node, index)

  def size(self):
    _, count = self.traversal(None)
    return count

  def search(self, data):
    node, _ = self.traversal(data)
    return node

  def add(self, data):
    node = Node(data)
    node.set_next(self.head)
    self.head = node

  def remove(self, data):
    previous_node = None
    current_node = self.head
    found = False
    while current_node is not None and not found:
      if current_node.get_data() == data:
        found = True
        if previous_node:
          previous_node.set_next(current_node.get_next())
        else:
          self.head = current_node
      else:
        previous_node = current_node
        current_node = current_node.get_next()
    return found

использование

link_list = LinkList()
link_list.add(10)
link_list.add(20)
link_list.add(30)
link_list.add(40)
link_list.add(50)
link_list.size()
link_list.search(30)
link_list.remove(20)

Оригинальная идея реализации

http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

мой двойной связанный список может быть понятен новичкам. Если вы знакомы с DS на C, это вполне читаемо.

# LinkedList..

class node:
    def __init__(self):           ##Cluster of Nodes' properties 
        self.data=None
        self.next=None
        self.prev=None

class linkedList():
    def __init__(self):
        self.t = node()                    // for future use
        self.cur_node = node()             // current node
        self.start=node()

    def add(self,data):                          // appending the LL

        self.new_node = node()
        self.new_node.data=data
        if self.cur_node.data is None:          
            self.start=self.new_node               //For the 1st node only

        self.cur_node.next=self.new_node
        self.new_node.prev=self.cur_node
        self.cur_node=self.new_node


    def backward_display(self):                  //Displays LL backwards
        self.t=self.cur_node
        while self.t.data is not None:
            print(self.t.data)
            self.t=self.t.prev

    def forward_display(self):                   //Displays LL Forward
        self.t=self.start
        while self.t.data is not None:
            print(self.t.data)
            self.t=self.t.next
            if self.t.next is None:
                print(self.t.data)
                break

    def main(self):                          //This is kind of the main 
                                               function in C
        ch=0
        while ch is not 4:                    //Switch-case in C 
            ch=int(input("Enter your choice:"))
            if ch is 1:
                data=int(input("Enter data to be added:"))
                ll.add(data)
                ll.main()
            elif ch is 2:
                ll.forward_display()
                ll.main()
            elif ch is 3:
                ll.backward_display()
                ll.main()
            else:
                print("Program ends!!")
                return


ll=linkedList()
ll.main()

Хотя к этому коду можно добавить еще много упрощений, я думал, что сырая реализация будет более понятной.

Я также написал единый связанный список на основе некоторого учебника, в котором есть два основных класса Node и Linked List, а также некоторые дополнительные методы для вставки, удаления, реверсирования, сортировки и т. д.

Это не самый лучший и не самый простой вариант, но работает нормально.

"""
????????????????

Single Linked List (SLL):
A simple object-oriented implementation of Single Linked List (SLL) 
with some associated methods, such as create list, count nodes, delete nodes, and such. 

????????????????
"""

class Node:
    """
    Instantiates a node
    """
    def __init__(self, value):
        """
        Node class constructor which sets the value and link of the node

        """
        self.info = value
        self.link = None

class SingleLinkedList:
    """
    Instantiates the SLL class
    """
    def __init__(self):
        """
        SLL class constructor which sets the value and link of the node

        """
        self.start = None

    def create_single_linked_list(self):
        """
        Reads values from stdin and appends them to this list and creates a SLL with integer nodes

        """
        try:
            number_of_nodes = int(input("?   Enter a positive integer between 1-50 for the number of nodes you wish to have in the list: "))
            if number_of_nodes <= 0 or number_of_nodes > 51:
                print("? The number of nodes though must be an integer between 1 to 50!")
                self.create_single_linked_list()

        except Exception as e:
            print("? Error: ", e)
            self.create_single_linked_list()


        try:
            for _ in range(number_of_nodes):
                try:
                    data = int(input("?   Enter an integer for the node to be inserted: "))
                    self.insert_node_at_end(data)
                except Exception as e:
                    print("? Error: ", e)
        except Exception as e:
            print("? Error: ", e)

    def count_sll_nodes(self):
        """
        Counts the nodes of the linked list

        """
        try:
            p = self.start
            n = 0
            while p is not None:
                n += 1
                p = p.link

            if n >= 1:
                print(f"? The number of nodes in the linked list is {n}")
            else:
                print(f"? The SLL does not have a node!")
        except Exception as e: 
            print("? Error: ", e)

    def search_sll_nodes(self, x):
        """
        Searches the x integer in the linked list
        """
        try:
            position =  1
            p = self.start
            while p is not None:
                if p.info == x:
                    print(f"? YAAAY! We found {x} at position {position}")
                    return True

                #Increment the position
                position += 1 
                #Assign the next node to the current node
                p = p.link
            else:
                print(f"? Sorry! We couldn't find {x} at any position. Maybe, you might want to use option 9 and try again later!")
                return False
        except Exception as e:
            print("? Error: ", e)

    def display_sll(self):
        """
        Displays the list
        """
        try:
            if self.start is None:
                print("? Single linked list is empty!")
                return

            display_sll = "? Single linked list nodes are: "
            p = self.start
            while p is not None:
                display_sll += str(p.info) + "\t"
                p = p.link

            print(display_sll)

        except Exception as e:
            print("? Error: ", e) 

    def insert_node_in_beginning(self, data):
        """
        Inserts an integer in the beginning of the linked list

        """
        try:
            temp = Node(data)
            temp.link = self.start
            self.start = temp
        except Exception as e:
            print("? Error: ", e)

    def insert_node_at_end(self, data):
        """
        Inserts an integer at the end of the linked list

        """
        try:            
            temp = Node(data)
            if self.start is None:
                self.start = temp
                return

            p = self.start  
            while p.link is not None:
                p = p.link
            p.link = temp
        except Exception as e:
            print("? Error: ", e)


    def insert_node_after_another(self, data, x):
        """
        Inserts an integer after the x node

        """
        try:
            p = self.start

            while p is not None:
                if p.info == x:
                    break
                p = p.link

            if p is None:
                print(f"? Sorry! {x} is not in the list.")
            else:
                temp = Node(data)
                temp.link = p.link
                p.link = temp
        except Exception as e: 
            print("? Error: ", e)


    def insert_node_before_another(self, data, x):
        """
        Inserts an integer before the x node

        """

        try:

            # If list is empty
            if self.start is None:
                print("? Sorry! The list is empty.")
                return 
            # If x is the first node, and new node should be inserted before the first node
            if x == self.start.info:
                temp = Node(data)
                temp.link = p.link
                p.link = temp

            # Finding the reference to the prior node containing x
            p = self.start
            while p.link is not None:
                if p.link.info == x:
                    break
                p = p.link

            if p.link is not None:
                print(f"? Sorry! {x} is not in the list.")
            else:
                temp = Node(data)
                temp.link = p.link
                p.link = temp           

        except Exception as e:
            print("? Error: ", e)

    def insert_node_at_position(self, data, k):
        """
        Inserts an integer in k position of the linked list

        """
        try:
            # if we wish to insert at the first node
            if k == 1:
                temp = Node(data)
                temp.link = self.start
                self.start = temp
                return

            p = self.start
            i = 1

            while i < k-1 and p is not None:
                p = p.link
                i += 1

            if p is None:
                print(f"? The max position is {i}") 
            else:    
                temp = Node(data)
                temp.link = self.start
                self.start = temp

        except Exception as e:
            print("? Error: ", e)

    def delete_a_node(self, x):
        """
        Deletes a node of a linked list

        """
        try:
            # If list is empty
            if self.start is None:
                print("? Sorry! The list is empty.")
                return

            # If there is only one node
            if self.start.info == x:
                self.start = self.start.link

            # If more than one node exists
            p = self.start
            while p.link is not None:
                if p.link.info == x:
                    break   
                p = p.link

            if p.link is None:
                print(f"? Sorry! {x} is not in the list.")
            else:
                p.link = p.link.link

        except Exception as e:
            print("? Error: ", e)

    def delete_sll_first_node(self):
        """
        Deletes the first node of a linked list

        """
        try:
            if self.start is None:
                return
            self.start = self.start.link

        except Exception as e:
            print("? Error: ", e)


    def delete_sll_last_node(self):
        """
        Deletes the last node of a linked list

        """
        try:

            # If the list is empty
            if self.start is None:
                return

            # If there is only one node
            if self.start.link is None:
                self.start = None
                return

            # If there is more than one node    
            p = self.start

            # Increment until we find the node prior to the last node 
            while p.link.link is not None:
                p = p.link

            p.link = None   

        except Exception as e:
            print("? Error: ", e)


    def reverse_sll(self):
        """
        Reverses the linked list

        """

        try:

            prev = None
            p = self.start
            while p is not None:
                next = p.link
                p.link = prev
                prev = p
                p = next
            self.start = prev

        except Exception as e:
            print("? Error: ", e)


    def bubble_sort_sll_nodes_data(self):
        """
        Bubble sorts the linked list on integer values

        """

        try:

            # If the list is empty or there is only one node
            if self.start is None or self.start.link is None:
                print("? The list has no or only one node and sorting is not required.")
            end = None

            while end != self.start.link:
                p = self.start
                while p.link != end:
                    q = p.link
                    if p.info > q.info:
                        p.info, q.info = q.info, p.info
                    p = p.link
                end = p

        except Exception as e:
            print("? Error: ", e)


    def bubble_sort_sll(self):
        """
        Bubble sorts the linked list

        """

        try:

            # If the list is empty or there is only one node
            if self.start is None or self.start.link is None:
                print("? The list has no or only one node and sorting is not required.")
            end = None

            while end != self.start.link:
                r = p = self.start
                while p.link != end:
                    q = p.link
                    if p.info > q.info:
                        p.link = q.link
                        q.link = p
                    if  p != self.start:
                        r.link = q.link
                    else:
                        self.start = q
                    p, q = q, p
                    r = p
                    p = p.link
                end = p

        except Exception as e:
            print("? Error: ", e)


    def sll_has_cycle(self):
        """
        Tests the list for cycles using Tortoise and Hare Algorithm (Floyd's cycle detection algorithm)
        """

        try:

            if self.find_sll_cycle() is None:
                return False
            else:
                return True


        except Exception as e:
            print("? Error: ", e)


    def find_sll_cycle(self):
        """
        Finds cycles in the list, if any
        """

        try:

            # If there is one node or none, there is no cycle
            if self.start is None or self.start.link is None:
                return None

            # Otherwise, 
            slowR = self.start
            fastR = self.start

            while slowR is not None and fastR is not None:
                slowR = slowR.link
                fastR = fastR.link.link
                if slowR == fastR: 
                    return slowR

            return None

        except Exception as e:
            print("? Error: ", e)


    def remove_cycle_from_sll(self):
        """
        Removes the cycles
        """

        try:

            c = self.find_sll_cycle()

            # If there is no cycle
            if c is None:
                return

            print(f"? There is a cycle at node: ", c.info)

            p = c
            q = c
            len_cycles = 0
            while True:
                len_cycles += 1
                q = q.link

                if p == q:
                    break

            print(f"? The cycle length is {len_cycles}")

            len_rem_list = 0
            p = self.start

            while p != q:
                len_rem_list += 1
                p = p.link
                q = q.link

            print(f"? The number of nodes not included in the cycle is {len_rem_list}")

            length_list = len_rem_list + len_cycles

            print(f"? The SLL length is {length_list}")

            # This for loop goes to the end of the SLL, and set the last node to None and the cycle is removed. 
            p = self.start
            for _ in range(length_list-1):
                p = p.link
            p.link = None


        except Exception as e:
            print("? Error: ", e)


    def insert_cycle_in_sll(self, x):
        """
        Inserts a cycle at a node that contains x

        """

        try:

            if self.start is None:
                return False

            p = self.start
            px = None
            prev = None


            while p is not None:
                if p.info == x:
                    px = p
                prev = p
                p = p.link

            if px is not None:
                prev.link = px
            else:
                print(f"? Sorry! {x} is not in the list.")


        except Exception as e:
            print("? Error: ", e)


    def merge_using_new_list(self, list2):
        """
        Merges two already sorted SLLs by creating new lists
        """
        merge_list = SingleLinkedList()
        merge_list.start = self._merge_using_new_list(self.start, list2.start)
        return merge_list

    def _merge_using_new_list(self, p1, p2):
        """
        Private method of merge_using_new_list
        """
        if p1.info <= p2.info:
            Start_merge = Node(p1.info)
            p1 = p1.link
        else:
            Start_merge = Node(p2.info)
            p2 = p2.link            
        pM = Start_merge

        while p1 is not None and p2 is not None:
            if p1.info <= p2.info:
                pM.link = Node(p1.info)
                p1 = p1.link
            else:
                pM.link = Node(p2.info)
                p2 = p2.link
            pM = pM.link

        #If the second list is finished, yet the first list has some nodes
        while p1 is not None:
            pM.link = Node(p1.info)
            p1 = p1.link
            pM = pM.link

        #If the second list is finished, yet the first list has some nodes
        while p2 is not None:
            pM.link = Node(p2.info)
            p2 = p2.link
            pM = pM.link

        return Start_merge

    def merge_inplace(self, list2):
        """
        Merges two already sorted SLLs in place in O(1) of space
        """
        merge_list = SingleLinkedList()
        merge_list.start = self._merge_inplace(self.start, list2.start)
        return merge_list

    def _merge_inplace(self, p1, p2):
        """
        Merges two already sorted SLLs in place in O(1) of space
        """
        if p1.info <= p2.info:
            Start_merge = p1
            p1 = p1.link
        else:
            Start_merge = p2
            p2 = p2.link
        pM = Start_merge

        while p1 is not None and p2 is not None:
            if p1.info <= p2.info:
                pM.link = p1
                pM = pM.link
                p1 = p1.link
            else:
                pM.link = p2
                pM = pM.link
                p2 = p2.link

        if p1 is None:
            pM.link = p2
        else:
            pM.link = p1

        return Start_merge

    def merge_sort_sll(self):
        """
        Sorts the linked list using merge sort algorithm
        """
        self.start = self._merge_sort_recursive(self.start)


    def _merge_sort_recursive(self, list_start):
        """
        Recursively calls the merge sort algorithm for two divided lists
        """

        # If the list is empty or has only one node
        if list_start is None or list_start.link is None:
            return list_start

        # If the list has two nodes or more
        start_one = list_start
        start_two = self._divide_list(self_start)
        start_one = self._merge_sort_recursive(start_one)
        start_two = self._merge_sort_recursive(start_two)
        start_merge = self._merge_inplace(start_one, start_two)

        return start_merge

    def _divide_list(self, p):
        """
        Divides the linked list into two almost equally sized lists
        """

        # Refers to the third nodes of the list
        q = p.link.link

        while q is not None and p is not None:
            # Increments p one node at the time
            p = p.link
            # Increments q two nodes at the time
            q = q.link.link

        start_two = p.link
        p.link = None

        return start_two

    def concat_second_list_to_sll(self, list2):
        """
        Concatenates another SLL to an existing SLL
        """

        # If the second SLL has no node
        if list2.start is None:
            return

        # If the original SLL has no node
        if self.start is None:
            self.start = list2.start
            return

        # Otherwise traverse the original SLL
        p = self.start
        while p.link is not None:
            p = p.link

        # Link the last node to the first node of the second SLL
        p.link = list2.start



    def test_merge_using_new_list_and_inplace(self):
        """

        """

        LIST_ONE = SingleLinkedList()
        LIST_TWO = SingleLinkedList()

        LIST_ONE.create_single_linked_list()
        LIST_TWO.create_single_linked_list()

        print("1️⃣  The unsorted first list is: ")
        LIST_ONE.display_sll()

        print("2️⃣  The unsorted second list is: ")
        LIST_TWO.display_sll()


        LIST_ONE.bubble_sort_sll_nodes_data()
        LIST_TWO.bubble_sort_sll_nodes_data()

        print("1️⃣  The sorted first list is: ")
        LIST_ONE.display_sll()

        print("2️⃣  The sorted second list is: ")
        LIST_TWO.display_sll()

        LIST_THREE = LIST_ONE.merge_using_new_list(LIST_TWO)

        print("The merged list by creating a new list is: ")
        LIST_THREE.display_sll()


        LIST_FOUR = LIST_ONE.merge_inplace(LIST_TWO)

        print("The in-place merged list is: ")
        LIST_FOUR.display_sll()     


    def test_all_methods(self):
        """
        Tests all methods of the SLL class
        """

        OPTIONS_HELP = """
?????????????????????????????????????????
    Select a method from 1-19:                                                          
?????????????????????????????????????????
        ℹ️   (1)    ?  Create a single liked list (SLL).
        ℹ️   (2)    ?  Display the SLL.                            
        ℹ️   (3)    ?  Count the nodes of SLL. 
        ℹ️   (4)    ?  Search the SLL.
        ℹ️   (5)    ?  Insert a node at the beginning of the SLL.
        ℹ️   (6)    ?  Insert a node at the end of the SLL.
        ℹ️   (7)    ?  Insert a node after a specified node of the SLL.
        ℹ️   (8)    ?  Insert a node before a specified node of the SLL.
        ℹ️   (9)    ?  Delete the first node of SLL.
        ℹ️   (10)   ?  Delete the last node of the SLL.
        ℹ️   (11)   ?  Delete a node you wish to remove.                           
        ℹ️   (12)   ?  Reverse the SLL.
        ℹ️   (13)   ?  Bubble sort the SLL by only exchanging the integer values.  
        ℹ️   (14)   ?  Bubble sort the SLL by exchanging links.                    
        ℹ️   (15)   ?  Merge sort the SLL.
        ℹ️   (16)   ?  Insert a cycle in the SLL.
        ℹ️   (17)   ?  Detect if the SLL has a cycle.
        ℹ️   (18)   ?  Remove cycle in the SLL.
        ℹ️   (19)   ?  Test merging two bubble-sorted SLLs.
        ℹ️   (20)   ?  Concatenate a second list to the SLL. 
        ℹ️   (21)   ?  Exit.
?????????????????????????????????????????
        """


        self.create_single_linked_list()

        while True:

            print(OPTIONS_HELP)

            UI_OPTION = int(input("?   Enter an integer for the method you wish to run using the above help: "))

            if UI_OPTION == 1:
                data = int(input("?   Enter an integer to be inserted at the end of the list: "))
                x = int(input("?   Enter an integer to be inserted after that: "))
                self.insert_node_after_another(data, x)
            elif UI_OPTION == 2:
                self.display_sll()
            elif UI_OPTION == 3:
                self.count_sll_nodes()
            elif UI_OPTION == 4:
                data = int(input("?   Enter an integer to be searched: "))
                self.search_sll_nodes(data)
            elif UI_OPTION == 5:
                data = int(input("?   Enter an integer to be inserted at the beginning: "))
                self.insert_node_in_beginning(data)
            elif UI_OPTION == 6:
                data = int(input("?   Enter an integer to be inserted at the end: "))
                self.insert_node_at_end(data)
            elif UI_OPTION == 7:
                data = int(input("?   Enter an integer to be inserted: "))
                x = int(input("?   Enter an integer to be inserted before that: "))
                self.insert_node_before_another(data, x)
            elif UI_OPTION == 8:
                data = int(input("?   Enter an integer for the node to be inserted: "))
                k = int(input("?   Enter an integer for the position at which you wish to insert the node: "))
                self.insert_node_before_another(data, k)
            elif UI_OPTION == 9:
                self.delete_sll_first_node()
            elif UI_OPTION == 10:
                self.delete_sll_last_node()
            elif UI_OPTION == 11:
                data = int(input("?   Enter an integer for the node you wish to remove: "))
                self.delete_a_node(data)
            elif UI_OPTION == 12:
                self.reverse_sll()
            elif UI_OPTION == 13:
                self.bubble_sort_sll_nodes_data()
            elif UI_OPTION == 14:
                self.bubble_sort_sll()
            elif UI_OPTION == 15:
                self.merge_sort_sll()
            elif UI_OPTION == 16:
                data = int(input("?   Enter an integer at which a cycle has to be formed: "))
                self.insert_cycle_in_sll(data)
            elif UI_OPTION == 17:
                if self.sll_has_cycle():
                    print("? The linked list has a cycle. ")
                else:
                    print("? YAAAY! The linked list does not have a cycle. ")
            elif UI_OPTION == 18:
                self.remove_cycle_from_sll()
            elif UI_OPTION == 19:
                self.test_merge_using_new_list_and_inplace()
            elif UI_OPTION == 20:
                list2 = self.create_single_linked_list()
                self.concat_second_list_to_sll(list2)
            elif UI_OPTION == 21:
                break
            else:
                print("? Option must be an integer, between 1 to 21.")

            print()     



if __name__ == '__main__':
    # Instantiates a new SLL object
    SLL_OBJECT = SingleLinkedList()
    SLL_OBJECT.test_all_methods()

Раскрывающий ответ Ника Стинматса

class Node(object):
    def __init__(self):
        self.data = None
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend_node(self, data):
        new_node = Node()
        new_node.data = data
        new_node.next = self.head
        self.head = new_node

    def append_node(self, data):
        new_node = Node()
        new_node.data = data
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def reverse(self):
        """ In-place reversal, modifies exiting list"""
        previous = None
        current_node = self.head

        while current_node:
            temp =  current_node.next
            current_node.next = previous
            previous = current_node
            current_node = temp
        self.head = previous

    def search(self, data):
        current_node = self.head
        try:
            while current_node.data != data:
                current_node = current_node.next
            return True
        except:
            return False

    def display(self):
        if self.head is None:
            print("Linked list is empty")
        else:
            current_node = self.head
            while current_node:
                print(current_node.data)
                current_node = current_node.next

    def list_length(self):
        list_length = 0
        current_node = self.head
        while current_node:
            list_length += 1
            current_node = current_node.next
        return list_length


def main():
    linked_list = LinkedList()

    linked_list.prepend_node(1)
    linked_list.prepend_node(2)
    linked_list.prepend_node(3)
    linked_list.append_node(24)
    linked_list.append_node(25)
    linked_list.display()
    linked_list.reverse()
    linked_list.display()
    print(linked_list.search(1))
    linked_list.reverse()
    linked_list.display()
    print("Lenght of singly linked list is: " + str(linked_list.list_length()))


if __name__ == "__main__":
    main()