Linked List

[alalbux]

Na ciência da computação, uma lista encadeada é uma coleção linear de elementos de dados, na qual a ordem linear não é dada por seu posicionamento físico na memória. Em vez disso, cada elemento aponta para o próximo. É uma estrutura de dados que consiste em um grupo de nós que juntos representam uma sequência. Sob a forma mais simples, cada nó é composto de dados e uma referência (em outras palavras, um link) para o próximo nó na sequência. Essa estrutura permite a inserção ou remoção eficiente de elementos de qualquer posição na seqüência durante a iteração. Variantes mais complexas adicionam links adicionais, permitindo a inserção ou remoção eficiente de referências de elementos arbitrárias. Uma desvantagem das listas vinculadas é que o tempo de acesso é linear (e difícil de pipeline). Acesso mais rápido, como acesso aleatório, não é viável. Matrizes têm melhor localidade de cache em comparação com listas vinculadas.

[alalbux]

https://en.wikipedia.org/wiki/Linked_list

[alalbux]

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

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

    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def get_position(self, position):
        counter = 1
        current = self.head
        if position < 1:
            return None
        while current and counter <= position:
            if counter == position:
                return current
            current = current.next
            counter += 1
        return None

    def insert(self, new_element, position):
        counter = 1
        current = self.head
        if position > 1:
            while current and counter < position:
                if counter == position - 1:
                    new_element.next = current.next
                    current.next = new_element
                current = current.next
                counter += 1
        elif position == 1:
            new_element.next = self.head
            self.head = new_element

    def delete(self, value):
        current = self.head
        previous = None
        while current.value != value and current.next:
            previous = current
            current = current.next
        if current.value == value:
            if previous:
                previous.next = current.next
            else:
                self.head = current.next