У цій статті ми дізнаємося про впровадження пов’язаного списку в Python . Щоб реалізувати пов’язаний список у Python, ми будемо використовувати класи на Python . Тепер ми знаємо, що пов’язаний список складається з вузлів, а вузли мають два елементи, тобто дані та посилання на інший вузол. Давайте спочатку реалізуємо вузол.
Що таке пов’язаний список у Python
Зв'язаний список це тип лінійної структури даних, подібний до масивів. Це набір вузлів, які пов’язані один з одним. Вузол містить дві речі: по-перше, це дані, а по-друге, це посилання, яке з’єднує його з іншим вузлом. Нижче наведено приклад пов’язаного списку з чотирма вузлами, і кожен вузол містить символьні дані та посилання на інший вузол. Наш перший вузол де голова точок, і ми можемо отримати доступ до всіх елементів пов’язаного списку за допомогою голова.
Зв'язаний список
Створення пов’язаного списку в Python
У цьому класі LinkedList ми будемо використовувати клас Node для створення пов’язаного списку. У цьому класі ми маємо __гарячий__ метод, який ініціалізує пов’язаний список із порожньою головою. Далі ми створили insertAtBegin() метод для вставки вузла на початку пов’язаного списку, an insertAtIndex() метод для вставки вузла за вказаним індексом пов’язаного списку та insertAtEnd() метод вставляє вузол у кінець пов’язаного списку. Після цього ми маємо remove_node() метод, який приймає дані як аргумент для видалення цього вузла. В remove_node() ми проходимо пов’язаний список, якщо присутній вузол, що дорівнює даним, тоді ми видаляємо цей вузол із зв’язаного списку. Тоді ми маємо sizeOfLL() метод для отримання поточного розміру пов’язаного списку та останній метод класу LinkedList printLL() який проходить пов’язаний список і друкує дані кожного вузла.
Створення класу вузла
Ми створили клас Node, у якому визначили a __гарячий__ функція для ініціалізації вузла з даними, переданими як аргумент, і посиланням з None, оскільки якщо у нас є лише один вузол, то в його посиланні нічого немає.
Python3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
>
>
Вставка в пов’язаний список
Вставка на початку пов’язаного списку
Цей метод вставляє вузол на початку пов’язаного списку. У цьому методі ми створюємо a новий_вузол з даним даних і перевірте, чи голова є порожнім вузлом чи ні, якщо голова порожня, тоді ми робимо новий_вузол як голова і повернення інакше ми вставляємо голову в наступний новий_вузол і зробити голова дорівнює новий_вузол.
Python3
def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> |
>
>
Вставте вузол у певну позицію в пов’язаному списку
Цей метод вставляє вузол за заданим індексом у пов’язаний список. У цьому методі ми створюємо a новий_вузол із заданими даними, поточним_вузлом, що дорівнює голові, та лічильником «позиція» ініціалізується за допомогою 0. Тепер, якщо індекс дорівнює нулю, це означає, що вузол потрібно вставити на початку, тому ми викликали метод insertAtBegin(). інакше ми виконуємо цикл while, поки не буде поточний_вузол не дорівнює Жодного або (позиція+1) не дорівнює індексу, який ми маємо на одну позицію назад, щоб вставити в задану позицію, щоб зробити зв’язування вузлів, і в кожній ітерації ми збільшуємо позицію на 1 і робимо поточний_вузол далі. Коли цикл розривається і якщо поточний_вузол не дорівнює Жодного ми вставляємо new_node у після поточний_вузол. Якщо поточний_вузол дорівнює Жодного це означає, що індекс відсутній у списку, і ми друкуємо Індекс відсутній.
Python3
складений первинний ключ
# Indexing starts from 0.> def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> |
>
>
Вставка в пов’язаний список у кінці
Цей метод вставляє вузол у кінець пов’язаного списку. У цьому методі ми створюємо a новий_вузол з наведеними даними та перевірте, чи голова є порожнім вузлом чи ні, якщо голова порожній, тоді ми робимо новий_вузол як голова і повернення інше ми робимо a поточний_вузол рівний до Глава траверс до останнього вузол пов’язаного списку та коли ми отримаємо Жодного після current_node цикл while розривається та вставляється новий_вузол у наступному з поточний_вузол який є останнім вузлом пов’язаного списку.
Python3
def> inserAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> |
>
>
Оновіть вузол пов’язаного списку
Цей код визначає метод під назвою updateNode у зв’язаному класі списку. Він використовується для оновлення значення вузла на заданій позиції у зв’язаному списку.
Python3
# Update node of a linked list> # at given position> def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> |
>
>
Видалити вузол у зв’язаному списку
Видалити перший вузол зі зв’язаного списку
Цей метод видаляє перший вузол пов’язаного списку, просто створюючи другий вузол голова пов’язаного списку.
Python3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
файл розширення java
>
Видалити останній вузол зі зв’язаного списку
У цьому методі ми видалимо останній вузол. Спочатку ми переходимо до передостаннього вузла за допомогою циклу while, а потім створюємо наступний з цього вузла Жодного і останній вузол буде видалено.
Python3
def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> |
>
>
Видалити вузол пов’язаного списку на певній позиції
У цьому методі ми видалимо вузол за заданим індексом, цей метод схожий на в insert_at_inded() метод. У цьому методі, якщо голова є Жодного ми просто повернення інакше ми ініціалізуємо a поточний_вузол з само.голова і положення з 0. Якщо позиція дорівнює індексу, який ми назвали remove_first_node() метод else, який ми переходимо до одного вузла, який ми хочемо видалити, використовуючи цикл while. Після цього, коли ми виходимо з циклу while, ми перевіряємо що поточний_вузол дорівнює Жодного якщо ні, тоді ми робимо наступний поточний_вузол рівним наступному вузлу, який ми хочемо видалити, інакше ми друкуємо повідомлення Індекс відсутній оскільки поточний_вузол дорівнює Жодного.
Python3
# Method to remove at given index> def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> |
>
>
Видалити вузол пов’язаного списку певних даних
Цей метод видаляє вузол із заданими даними зі зв’язаного списку. У цьому методі спочатку ми зробили a поточний_вузол дорівнює голова і запустіть a цикл while для перегляду пов’язаного списку. Цей цикл while розривається, коли поточний_вузол стає Жодного або дані поруч із поточним вузлом дорівнюють даним, наведеним у аргументі. Тепер, після виходу з циклу, якщо поточний_вузол дорівнює Жодного це означає, що вузол відсутній у даних, і ми просто повертаємося, і якщо дані поруч із поточний_вузол дорівнює наданим даним, тоді ми видаляємо цей вузол, перетворюючи наступний з видаленого_вузла на наступний з поточного_вузла. І це реалізовано за допомогою умови if else.
Python3
def> remove_node(>self>, data):> >current_node>=> self>.head> ># Check if the head node contains the specified data> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while> current_node>is> not> None> and> current_node.>next>.data !>=> data:> >current_node>=> current_node.>next> >if> current_node>is> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> |
>
>
Обхід пов’язаного списку в Python
Цей метод проходить пов’язаний список і друкує дані кожного вузла. У цьому методі ми зробили a поточний_вузол дорівнює голова і перебирайте пов’язаний список за допомогою a цикл while до поточний_вузол стати None і надрукувати дані поточний_вузол у кожній ітерації та зробити поточний_вузол поруч з ним.
Python3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Отримати довжину пов’язаного списку в Python
Цей метод повертає розмір пов’язаного списку. У цьому методі ми ініціалізували лічильник «розмір» з 0, а потім, якщо заголовок не дорівнює None, ми проходимо пов’язаний список за допомогою a цикл while і збільшити розмір з 1 у кожній ітерації та повертати розмір, коли поточний_вузол стає Більше ніхто повертаємо 0.
Python3
def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> |
>
>
Приклад пов’язаного списку в Python
У цьому прикладі після визначення класу Node і LinkedList ми створили пов’язаний список з назвою список використовуючи клас пов’язаного списку, а потім вставте чотири вузли з символьними даними 'а Б В Г' і «g» у зв’язаному списку, тоді ми друкуємо зв’язаний список за допомогою printLL() після цього ми видалили деякі вузли за допомогою методів видалення а потім знову роздрукувати пов’язаний список, і ми побачимо у виводі, що вузол успішно видалено. Після цього ми також друкуємо розмір пов’язаного списку.
Python3
string.format рядок java
# Create a Node class to create a node> class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> # Create a LinkedList class> class> LinkedList:> >def> __init__(>self>):> >self>.head>=> None> ># Method to add a node at begin of LL> >def> insertAtBegin(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >else>:> >new_node.>next> => self>.head> >self>.head>=> new_node> ># Method to add a node at any index> ># Indexing starts from 0.> >def> insertAtIndex(>self>, data, index):> >new_node>=> Node(data)> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.insertAtBegin(data)> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >new_node.>next> => current_node.>next> >current_node.>next> => new_node> >else>:> >print>(>'Index not present'>)> ># Method to add a node at the end of LL> >def> insertAtEnd(>self>, data):> >new_node>=> Node(data)> >if> self>.head>is> None>:> >self>.head>=> new_node> >return> >current_node>=> self>.head> >while>(current_node.>next>):> >current_node>=> current_node.>next> >current_node.>next> => new_node> ># Update node of a linked list> ># at given position> >def> updateNode(>self>, val, index):> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >current_node.data>=> val> >else>:> >while>(current_node !>=> None> and> position !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.data>=> val> >else>:> >print>(>'Index not present'>)> ># Method to remove first node of linked list> >def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> >self>.head>=> self>.head.>next> ># Method to remove last node of linked list> >def> remove_last_node(>self>):> >if> self>.head>is> None>:> >return> >current_node>=> self>.head> >while>(current_node.>next>.>next>):> >current_node>=> current_node.>next> >current_node.>next> => None> ># Method to remove at given index> >def> remove_at_index(>self>, index):> >if> self>.head>=>=> None>:> >return> >current_node>=> self>.head> >position>=> 0> >if> position>=>=> index:> >self>.remove_first_node()> >else>:> >while>(current_node !>=> None> and> position>+>1> !>=> index):> >position>=> position>+>1> >current_node>=> current_node.>next> >if> current_node !>=> None>:> >current_node.>next> => current_node.>next>.>next> >else>:> >print>(>'Index not present'>)> ># Method to remove a node from linked list> >def> remove_node(>self>, data):> >current_node>=> self>.head> >if> current_node.data>=>=> data:> >self>.remove_first_node()> >return> >while>(current_node !>=> None> and> current_node.>next>.data !>=> data):> >current_node>=> current_node.>next> >if> current_node>=>=> None>:> >return> >else>:> >current_node.>next> => current_node.>next>.>next> ># Print the size of linked list> >def> sizeOfLL(>self>):> >size>=> 0> >if>(>self>.head):> >current_node>=> self>.head> >while>(current_node):> >size>=> size>+>1> >current_node>=> current_node.>next> >return> size> >else>:> >return> 0> ># print method for the linked list> >def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> # create a new linked list> llist>=> LinkedList()> # add nodes to the linked list> llist.insertAtEnd(>'a'>)> llist.insertAtEnd(>'b'>)> llist.insertAtBegin(>'c'>)> llist.insertAtEnd(>'d'>)> llist.insertAtIndex(>'g'>,>2>)> # print the linked list> print>(>'Node Data'>)> llist.printLL()> # remove a nodes from the linked list> print>(>'
Remove First Node'>)> llist.remove_first_node()> print>(>'Remove Last Node'>)> llist.remove_last_node()> print>(>'Remove Node at Index 1'>)> llist.remove_at_index(>1>)> # print the linked list again> print>(>'
Linked list after removing a node:'>)> llist.printLL()> print>(>'
Update node Value'>)> llist.updateNode(>'z'>,>0>)> llist.printLL()> print>(>'
Size of linked list :'>, end>=>' '>)> print>(llist.sizeOfLL())> |
>
>Вихід
Node Data c a g b d Remove First Node Remove Last Node Remove Node at Index 1 Linked list after removing a node: a b Update node Value z b Size of linked list : 2>