Ahogy a füzér virágokkal készül, a csatolt lista csomópontokból áll. Az adott füzér minden virágát csomópontnak hívjuk. És mindegyik csomópont a lista következő csomópontjára mutat, valamint rendelkezik adatokkal (itt ez a virág típusa).
Típusok
Egyszerűen összekapcsolt lista
Az egyesével összekapcsolt listák olyan csomópontokat tartalmaznak, amelyeknek van data
mezője, valamint next
mezője, amely a sorozat következő csomópontjára mutat. Az egymással összekapcsolt listákon végrehajtható műveletek a beillesztés, a törlés és a bejárás.
head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+
A CPython belső megvalósítása, a keretek és az értékelt változók veremben vannak.
Ehhez csak előre kell fordítanunk az aur-t, hogy megkapja a fejét, ezért egyedül linkelt listát használunk.
Kétségkívül összekapcsolt lista
A kétszeresen összekapcsolt listák tartalmaznak olyan csomópontot, amelynek data
mezője, next
mezője és egy másik prev
linkmezője a sorozat előző csomópontjára mutat.
head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+
A böngésző gyorsítótára, amely lehetővé teszi a VISSZA és ELŐRE gomb megnyomását. Itt fenn kell tartanunk egy kétszeresen összekapcsolt listát, URLs
mint adatmező, hogy mindkét irányba hozzáférhessünk. Az előző URL-hez a prev
mezőt fogjuk használni , a következő oldalra pedig a next
mezőt fogjuk használni .
Kör alakú összekapcsolt lista
A körkörös összekapcsolt listák egyenként összekapcsolt listák, amelyekben az utolsó next
mezõ a mezõ a szekvencia elsõ csomópontjára mutat.
head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+
Az időmegosztás problémáját az operációs rendszer megoldotta.
Időmegosztásos környezetben az operációs rendszernek karban kell tartania a jelenlegi felhasználók listáját, és váltakozva lehetővé kell tennie minden felhasználó számára, hogy egyszerre csak egy felhasználót használjon a CPU idő kis részében. Az operációs rendszer kiválaszt egy felhasználót, hagyja, hogy egy kis CPU-időt használjon, majd továbblépjen a következő felhasználóhoz.
Ehhez az alkalmazáshoz nem lehet NULL mutató, hacsak egyáltalán nincs olyan, aki CPU-időt kérne, azaz a lista üres.
Alapműveletek
Beszúrás
Új elem hozzáadása a listához.
Beszúrás az elején:
- Hozzon létre egy új csomópontot a megadott adatokkal.
- Mutasson új csomópontot
next
a régirehead
. - Mutasson
head
erre az új csomópontra.
Beillesztés a közepébe / végébe.
Beszúrás az X csomópont után.
- Hozzon létre egy új csomópontot a megadott adatokkal.
- Mutasson új csomópontokat
next
a régi X-ekrenext
. - X pont
next
erre az új csomópontra.
Időkomplexum: O (1)
Törlés
Meglévő elem törlése a listáról.
Törlés az elején
- Szerezd meg a csomópontot
head
Hőm. - Mutasson
head
a Temp's-ranext
. - A Temp csomópont által használt szabad memória.
Törlés a közepén / végén.
Törlés az X csomópont után.
- Szerezd meg a csomópontot
X
Hőm. - X pont
next
a hőmérsékletheznext
. - A Temp csomópont által használt szabad memória.
Időkomplexum: O (1)
Traversing
Utazni a listán.
Traversal
- Szerezd meg a csomópontot
head
aktuálisként. - Ellenőrizze, hogy a Current nem null, és jelenítse meg.
- Mutasson az Áram áramra
next
és lépjen a fenti lépésre.
Időkomplexitás: O (n) // Itt n a linklista mérete
Végrehajtás
Egyszerűen összekapcsolt lista C ++ megvalósítása
// Header files #include struct node { int data; struct node *next; }; // Head pointer always points to first element of the linked list struct node *head = NULL;
Adatok nyomtatása az egyes csomópontokban
// Display the list void printList() { struct node *ptr = head; // Start from the beginning while(ptr != NULL) { std::cout
Insertion at the beginning
// 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; }
Deletion at the beginning
// 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; }
Size
// 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; }
Searching
// 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" next == NULL){ std::cout << "Not Found"
Deletion after a node
Deletion after a node
// 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" next == NULL){ std::cout << "Element not found"
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; }
Python Implementation of Singly Linked List
Python Implementation of Singly Linked List
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
Insertion
Insertion
# 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")
Size
Size
# 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))
Searching
Searching
# 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")
Deletion after a node
Deletion after a node
# 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")
Advantages
Linked lists are a dynamic data structure, which can grow and shrink, allocating and deallocating memory while the program is running.
Insertion and deletion of node are easily implemented in a linked list at any position.
Disadvantages
They use more memory than arrays because of the memory used by their pointers (
next
andprev
).Random access is not possible in linked list. We have to access nodes sequentially.
It’s more complex than array. If a language supports array bound check automatically, Arrays would serve you better.
Note
Note
We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.