Neste tutorial, você aprenderá sobre a estrutura de dados de lista vinculada e sua implementação em Python, Java, C e C ++.
Uma estrutura de dados de lista vinculada inclui uma série de nós conectados. Aqui, cada nó armazena os dados e o endereço do próximo nó. Por exemplo,
Estrutura de dados LinkedList
Você tem que começar em algum lugar, então damos ao endereço do primeiro nó um nome especial chamado HEAD.
Além disso, o último nó na lista vinculada pode ser identificado porque sua próxima parte aponta para NULL.
Você pode ter jogado o jogo Caça ao Tesouro, onde cada pista inclui as informações sobre a próxima pista. É assim que a lista vinculada funciona.
Representação de LinkedList
Vamos ver como cada nó da LinkedList é representado. Cada nó consiste em:
- Um item de dados
- Um endereço de outro nó
Envolvemos o item de dados e a próxima referência de nó em uma estrutura como:
struct node ( int data; struct node *next; );
Entender a estrutura de um nó de lista vinculada é a chave para entendê-la.
Cada nó de estrutura possui um item de dados e um ponteiro para outro nó de estrutura. Vamos criar uma lista vinculada simples com três itens para entender como isso funciona.
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data=3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Se você não entendeu nenhuma das linhas acima, tudo o que você precisa é uma atualização sobre as dicas e estruturas.
Em apenas algumas etapas, criamos uma lista vinculada simples com três nós.
Representação LinkedList
O poder do LinkedList vem da capacidade de quebrar a cadeia e voltar a aderir a ela. Por exemplo, se você quiser colocar um elemento 4 entre 1 e 2, as etapas serão:
- Crie um novo nó de estrutura e aloque memória para ele.
- Adicione seu valor de dados como 4
- Aponte seu próximo ponteiro para o nó da estrutura contendo 2 como o valor dos dados
- Mude o próximo ponteiro de "1" para o nó que acabamos de criar.
Fazer algo semelhante em uma matriz exigiria mudar as posições de todos os elementos subsequentes.
Em python e Java, a lista vinculada pode ser implementada usando classes conforme mostrado nos códigos abaixo.
Utilitário de lista vinculada
Listas são uma das estruturas de dados mais populares e eficientes, com implementação em todas as linguagens de programação como C, C ++, Python, Java e C #.
Além disso, as listas vinculadas são uma ótima maneira de aprender como os ponteiros funcionam. Ao praticar como manipular listas vinculadas, você pode se preparar para aprender estruturas de dados mais avançadas, como gráficos e árvores.
Implementações de lista vinculada em exemplos Python, Java, C e C ++
Python Java C C + # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next
// Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )
// Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )
// Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )
Complexidade da lista vinculada
Complexidade de tempo
| Pior caso | Caso Médio | |
|---|---|---|
| Pesquisa | Em) | Em) |
| Inserir | O (1) | O (1) |
| Eliminação | O (1) | O (1) |
Complexidade do espaço: O (n)
Aplicativos de lista vinculada
- Alocação de memória dinâmica
- Implementado em pilha e fila
- Em desfazer a funcionalidade de softwares
- Tabelas de hash, gráficos
Leituras Recomendadas
1. Tutoriais
- Operações LinkedList (Traverse, Insert, Delete)
- Tipos de LinkedList
- Java LinkedList
2. Exemplos
- Obtenha o elemento do meio de LinkedList em uma única iteração
- Converta a LinkedList em um Array e vice-versa
- Detectar loop em uma LinkedList
