La fel cum o ghirlandă este făcută cu flori, o listă legată este formată din noduri. Numim fiecare floare de pe această ghirlandă să fie un nod. Și fiecare dintre noduri indică următorul nod din această listă, precum și date (aici este tipul de floare).

Tipuri

Listă legată individual

Listele conectate individual conțin noduri care au un data câmp precum și a next , care indică următorul nod din secvență. Operațiile care pot fi efectuate pe liste legate individual sunt inserarea, ștergerea și traversarea.

   head
    |
    |
  +-----+--+      +-----+--+      +-----+------+
  |  1  |o----->  |  2  |o----->  |  3  | NULL |
  +-----+--+      +-----+--+      +-----+------+

Implementarea internă a CPython, cadrele și variabilele evaluate sunt păstrate pe o stivă.

Pentru aceasta trebuie să repetăm ​​doar înainte să obținem capul, prin urmare se folosește o listă legată individual.

Lista dublă legată

Listele legate dublu conțin nod care au data camp, next și un alt câmp de legătură prev arătând spre nodul anterior din secvență.

          head
           |
           |
  +------+-----+--+    +--+-----+--+       +-----+------+
  |      |     |o------>  |     |o------>  |     |      |
  | NULL |  1  |          |  2  |          |  3  | NULL |
  |      |     |  <------o|     |  <------o|     |      |
  +------+-----+--+    +--+-----+--+       +-----+------+

Cache-ul browserului care vă permite să apăsați butoanele BACK și FORWARD. Aici trebuie să menținem o listă dublă legată, cu URLs ca câmp de date, pentru a permite accesul în ambele direcții. Pentru a merge la URL-ul anterior vom folosi prev câmp și pentru a merge la pagina următoare vom folosi next camp.

Listă circulară legată

Listele circulare conectate este o listă legată individual în care ultimul nod, next câmpul indică primul nod din secvență.

     head
      |
      |
    +-----+--+      +-----+--+      +-----+--+
    —> | 1 |o-----> | 2 |o----->    | 3 |o----| 
    +-----+--+      +-----+--+      +-----+--+

Problemă de partajare rezolvată de sistemul de operare.

Într-un mediu de partajare a timpului, sistemul de operare trebuie să mențină o listă de utilizatori actuali și trebuie să permită alternativ fiecărui utilizator să folosească o mică parte din timpul procesorului, câte un utilizator la un moment dat. Sistemul de operare va alege un utilizator, îl va lăsa să folosească o cantitate mică de timp CPU și apoi să treacă la următorul utilizator.

Pentru această aplicație, nu ar trebui să existe indicatori NULL, cu excepția cazului în care nu există absolut nimeni care să solicite timpul CPU, adică lista este goală.

Operațiuni de bază

Inserare

Pentru a adăuga un element nou la listă.

Inserare la început:

  • Creați un nod nou cu datele date.
  • Indicați un nod nou next prea bătran head.
  • Punct head către acest nou nod.

Inserare la mijloc / capăt.

Inserare după nodul X.

  • Creați un nod nou cu datele date.
  • Indicați un nod nou next la vechile X. next.
  • Punctul X. next la acest nou nod.

Complexitatea timpului: O (1)

Ștergere

Pentru a șterge elementul existent din listă.

Ștergerea la început

  • Obțineți nodul indicat de head ca Temp.
  • Punct head la Temp next.
  • Memorie liberă utilizată de nodul Temp.

Ștergere la mijloc / sfârșit.

Ștergerea după nodul X.

  • Obțineți nodul indicat de X ca Temp.
  • Punctul X. next la Temp next.
  • Memorie liberă utilizată de nodul Temp.

Complexitatea timpului: O (1)

Traversare

Pentru a călători pe listă.

Traversal

  • Obțineți nodul indicat de head ca Curent.
  • Verificați dacă Current nu este nul și afișați-l.
  • Punct curent la curent next și treceți la pasul de deasupra.

Complexitatea timpului: O (n) // Aici n este dimensiunea listei de linkuri

Implementare

Implementarea C ++ a listei legate individual

// Header files
#include <iostream>

struct node
{
    int data;
    struct node *next;
};

// Head pointer always points to first element of the linked list
struct node *head = NULL;

Imprimarea datelor în fiecare nod

// Display the list
void printList()
{
    struct node *ptr = head;

    // Start from the beginning
while(ptr != NULL)
{
    std::cout << ptr->data << " ";
    ptr = ptr->next;
}

std::cout << std::endl;
}

Inserare la început

// Insert link at the beginning
void insertFirst(int data)
{
    // Create a new node
    struct node *new_node = new struct node;

    new_node->data = data;

// Point it to old head
new_node->next = head;

// Point head to new node
head = new_node;

std::cout << "Inserted successfully" << std::endl;
}

Ștergerea la început

// Delete first item
void deleteFirst()
{
    // Save reference to head
    struct node *temp = head;

    // Point head to head's next
head = head->next;

// Free memory used by temp
temp = NULL:
delete temp;

std::cout << "Deleted successfully" << std::endl;
}

mărimea

// Find no. of nodes in link list
void size()
{
    int length = 0;
    struct node *current;

    for(current = head; current != NULL; current = current->next)
{
    length++;
}

std::cout << "Size of Linked List is " << length << std::endl;
}

In cautarea

// Find node with given data
void find(int data){

    // Start from the head
struct node* current = head;

// If list is empty
if(head == NULL)
{
    std::cout << "List is empty" << std::endl;
    return;
}

// Traverse through list
while(current->data != data){

    // If it is last node
    if(current->next == NULL){
        std::cout << "Not Found" << std::endl;
        return;
    }
    else{
        // Go to next node
        current = current->next;
    }
}

// If data found
std::cout << "Found" << std::endl;
}

Ștergerea după un nod

// Delete a node with given data
void del(int data){

    // Start from the first node
struct node* current = head;
struct node* previous = NULL;

// If list is empty
if(head == NULL){
    std::cout << "List is empty" << std::endl;
    return ;
}

// Navigate through list
while(current->data != data){

    // If it is last node
    if(current->next == NULL){
        std::cout << "Element not found" << std::endl;
        return ;
    }
    else {
        // Store reference to current node
        previous = current;
        // Move to next node
        current = current->next;
    }

}

// Found a match, update the node
if(current == head) {
    // Change head to point to next node
    head = head->next;
}
else {
    // Skip the current node
    previous->next = current->next;
}

// Free space used by deleted node
current = NULL;
delete current;
std::cout << "Deleted succesfully" << std::endl;
}

Implementarea Python a listei cu legături individuale

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

    # Function to get data
def get_data(self):
    return self.data

# Function to get next node
def get_next(self):
    return self.next

# Function to set next field
def set_next(self, new_next):
    self.next = new_next
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

Inserare

    # Function to insert data
def insert(self, data):
    # new_node is a object of class Node
    new_node = Node(data)
    new_node.set_next(self.head)
    self.head = new_node
    print("Node with data " + str(data) + " is created succesfully")

mărimea

    # Function to get size
def size(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.get_next()
    print("Size of link list is " + str(count))

In cautarea

    # Function to search a data
def search(self, data):
    current = self.head
    found = False
    while current and found is False:
        if current.get_data() == data:
            found = True
        else:
            current = current.get_next()
    if current is None:
        print("Node with data " + str(data) + " is not present")
    else:
        print("Node with data " + str(data) + " is found")

Ștergerea după un nod

    # Function to delete a node with data
def delete(self, data):
    current = self.head
    previous = None
    found = False
    while current and found is False:
        if current.get_data() == data:
            found = True
        else:
            previous = current
            current = current.get_next()
    if current is None:
        print("Node with data " + str(data) + " is not in list")
    elif previous is None:
        self.head = current.get_next()
        print("Node with data " + str(data) + " is deleted successfully")
    else:
        previous.set_next(current.get_next())
        print("Node with data " + str(data) + " is deleted successfully")

Avantaje

  1. Listele legate sunt o structură de date dinamică, care poate crește și micșora, alocând și alocând memoria în timp ce programul rulează.
  2. Inserarea și ștergerea nodului sunt ușor implementate într-o listă legată în orice poziție.

Dezavantaje

  1. Folosesc mai multă memorie decât matrice din cauza memoriei folosite de pointerii lor (next și prev).
  2. Accesul aleatoriu nu este posibil în lista conectată. Trebuie să accesăm nodurile secvențial.
  3. Este mai complex decât matricea. Dacă o limbă acceptă verificarea legată de matrice în mod automat, matricile vă vor servi mai bine.

Notă

Trebuie să folosim free () în C și să ștergem în C ++ pentru a elibera spațiul folosit de nodul șters, în timp ce, în Python și Java, spațiul liber este colectat automat de către colectorul de gunoi.