Структура данных «Список». Виды списков.

Определения

Связный список (англ. List) — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.

Односвязный список

1. Односвязный - ссылка на next или prev

class LinkedList:  
    def __init__(self, data):  
        self.next = None  
        self.data = data  
	  
    def append(self, val):  
        end = LinkedList(val)  
        n = self  
        while n.next:  
            n = n.next  
        n.next = end

Двусвязный список

2. Двусвязный - ссылки на next и prev

class DoublyLinkedList:  
    def __init__(self, data):  
        self.prev = None  
        self.next = None  
        self.data = data  
	  
    def appendRight(self, val):  
        right = DoublyLinkedList(val)  
        n = self  
        while n.next:  
            n = n.next  
        n.next = right  
        right.prev = n  
	  
    def appendLeft(self, val):  
        left = DoublyLinkedList(val)  
        n = self  
        while n.prev:  
            n = n.prev  
        n.prev = left  
        left.next = n

Циклический список

3. Циклический - когда ссылка последнего элемента ведет на первый или наоборот