이번 포스팅에서는 연결리스트 구현에 대해 알아보겠습니다. 파이썬 . Python에서 연결리스트를 구현하기 위해 다음을 사용합니다. Python의 클래스 . 이제 우리는 연결된 목록이 노드로 구성되고 노드에는 데이터와 다른 노드에 대한 참조라는 두 가지 요소가 있다는 것을 알고 있습니다. 먼저 노드를 구현해 보겠습니다.
Python의 연결리스트란?
연결 목록 배열과 유사한 선형 데이터 구조 유형입니다. 서로 연결된 노드의 집합입니다. 노드에는 두 가지가 포함됩니다. 첫째는 데이터이고, 둘째는 노드를 다른 노드와 연결하는 링크입니다. 다음은 4개의 노드가 있는 연결 목록의 예이며 각 노드에는 문자 데이터와 다른 노드에 대한 링크가 포함되어 있습니다. 첫 번째 노드는 다음과 같습니다. 머리 포인트를 사용하여 연결 리스트의 모든 요소에 접근할 수 있습니다. 머리.
연결리스트
Python에서 연결리스트 만들기
이 LinkedList 클래스에서는 Node 클래스를 사용하여 연결 목록을 만듭니다. 이 수업에서 우리는 __더운__ 빈 헤드로 연결된 목록을 초기화하는 메서드입니다. 다음으로 우리는 insertAtBegin() 연결리스트의 시작 부분에 노드를 삽입하는 방법 insertAtIndex() 연결리스트의 특정 인덱스에 노드를 삽입하는 방법 insertAtEnd() 메서드는 연결된 목록의 끝에 노드를 삽입합니다. 그 후, 우리는 제거_노드() 데이터를 인수로 사용하여 해당 노드를 삭제하는 메서드입니다. 에서 제거_노드() 이 방법에서는 노드가 데이터와 동일하게 존재하면 연결 목록을 순회한 다음 연결 목록에서 해당 노드를 삭제합니다. 그러면 우리는 sizeOfLL() 연결된 목록의 현재 크기를 가져오는 메서드와 LinkedList 클래스의 마지막 메서드는 다음과 같습니다. 인쇄LL() 연결된 목록을 순회하고 각 노드의 데이터를 인쇄합니다.
노드 클래스 생성
우리는 다음을 정의한 Node 클래스를 만들었습니다. __더운__ 함수는 인수로 전달된 데이터와 None을 사용하여 참조로 노드를 초기화합니다. 왜냐하면 노드가 하나만 있으면 참조에 아무것도 없기 때문입니다.
파이썬3
class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.>next> => None> |
스위치 케이스 자바
>
>
연결리스트에 삽입
연결리스트의 시작 부분에 삽입
이 메서드는 연결된 목록의 시작 부분에 노드를 삽입합니다. 이 방법에서는 new_node 주어진 것과 함께 데이터 헤드가 빈 노드인지 확인하고 헤드가 비어 있는지 확인한 다음 new_node ~처럼 머리 그리고 반품 그렇지 않으면 다음에 머리를 삽입합니다. new_node 그리고 만들어라 머리 동일 new_node.
파이썬3
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> |
>
>
연결리스트의 특정 위치에 노드 삽입
이 메서드는 연결된 목록의 지정된 인덱스에 노드를 삽입합니다. 이 방법에서는 new_node 주어진 데이터, 헤드와 동일한 current_node 및 카운터 '위치' 다음으로 초기화 0. 이제 인덱스가 0이면 노드가 시작 부분에 삽입된다는 의미이므로 다음을 호출했습니다. insertAtBegin() 메서드 그렇지 않으면 우리는 다음이 나올 때까지 while 루프를 실행합니다. 현재_노드 같지 않다 없음 또는 (위치+1) 노드를 연결하기 위해 주어진 위치에 삽입하기 위해 한 위치에서 다시 필요한 인덱스와 같지 않으며 각 반복에서 위치를 1씩 증가시키고 현재_노드 그 다음. 루프가 끊어지는 경우 현재_노드 같지 않다 없음 new_node를 뒤에 삽입합니다. 현재_노드. 만약에 현재_노드 동일하다 없음 이는 인덱스가 목록에 없으며 인쇄한다는 의미입니다. 인덱스가 없습니다.
파이썬3
# 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'>)> |
>
>
연결리스트 끝에 삽입
이 메서드는 연결된 목록의 끝에 노드를 삽입합니다. 이 방법에서는 new_node 주어진 데이터로 머리 빈 노드이거나 그렇지 않은 경우 머리 비어 있으면 다음을 만듭니다. new_node ~처럼 머리 그리고 반품 또 다른 우리는 current_node가 같음 에게 머리 마지막까지 횡단하다 마디 연결된 목록의 그리고 우리가 얻을 때 없음 current_node 다음에 while 루프가 중단되고 삽입됩니다. new_node 다음에는 현재_노드 연결리스트의 마지막 노드이다.
파이썬3
여우와 늑대의 차이
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라는 메서드를 정의합니다. 연결된 목록의 특정 위치에 있는 노드의 값을 업데이트하는 데 사용됩니다.
파이썬3
# 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'>)> |
>
>
연결리스트에서 노드 삭제
연결리스트에서 첫 번째 노드 제거
이 방법은 단순히 두 번째 노드를 만들어 연결리스트의 첫 번째 노드를 제거합니다. 머리 연결리스트의.
파이썬3
def> remove_first_node(>self>):> >if>(>self>.head>=>=> None>):> >return> > >self>.head>=> self>.head.>next> |
>
>
연결리스트에서 마지막 노드 제거
이 방법에서는 마지막 노드를 삭제합니다. 먼저 while 루프를 사용하여 두 번째 마지막 노드로 이동한 다음 해당 노드의 다음 노드를 만듭니다. 없음 마지막 노드가 제거됩니다.
파이썬3
삽입 정렬 자바
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() 방법. 이 방법의 경우, 머리 ~이다 없음 우리는 단순히 반품 그렇지 않으면 우리는 현재_노드 ~와 함께 자기 머리 그리고 위치 ~와 함께 0. 위치가 인덱스와 같으면 제거_첫번째_노드() 그렇지 않으면 while 루프를 사용하여 제거하려는 노드 앞에 있는 노드로 이동합니다. 그 후 while 루프에서 벗어날 때 확인합니다. 해당 current_node 동일하다 없음 그렇지 않은 경우 current_node의 다음 항목을 제거하려는 노드의 다음 항목과 동일하게 만들고 그렇지 않으면 메시지를 인쇄합니다. 인덱스가 존재하지 않음 왜냐하면 현재_노드 동일하다 없음.
파이썬3
# 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'>)> |
>
>
주어진 데이터의 연결 목록 노드 삭제
이 메서드는 연결된 목록에서 주어진 데이터가 있는 노드를 제거합니다. 이 방법에서는 먼저 현재_노드 와 같다 머리 그리고 실행 while 루프 연결리스트를 순회하는 것입니다. 이 while 루프는 다음과 같은 경우에 중단됩니다. 현재_노드 된다 없음 또는 현재 노드 옆의 데이터가 인수에 제공된 데이터와 같습니다. 이제 루프에서 나온 후 현재_노드 동일하다 없음 이는 해당 노드가 데이터에 존재하지 않고 그냥 반환된다는 의미입니다. 현재_노드 주어진 데이터와 같으면 제거된_노드 다음을 현재_노드의 다음으로 만들어 해당 노드를 제거합니다. 그리고 이는 if else 조건을 사용하여 구현됩니다.
파이썬3
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의 연결 목록 탐색
이 메서드는 연결된 목록을 순회하여 각 노드의 데이터를 인쇄합니다. 이 방법으로 우리는 현재_노드 와 같다 머리 그리고 다음을 사용하여 연결된 목록을 반복합니다. while 루프 까지 현재_노드 None이 되고 다음의 데이터를 인쇄합니다. 현재_노드 각 반복에서 현재_노드 그 옆에.
자바 문자열이 비어 있습니다
파이썬3
def> printLL(>self>):> >current_node>=> self>.head> >while>(current_node):> >print>(current_node.data)> >current_node>=> current_node.>next> |
>
>
Python에서 연결 목록의 길이 가져오기
이 메서드는 연결된 목록의 크기를 반환합니다. 이 방법에서는 카운터를 초기화했습니다. '크기' 0으로, 그리고 헤드가 None이 아니면 우리는 다음을 사용하여 연결된 목록을 탐색합니다. while 루프 그리고 증가 크기 각 반복마다 1을 사용하고 다음 경우 크기를 반환합니다. 현재_노드 된다 그 외 없음 우리는 0을 반환합니다.
파이썬3
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 클래스를 정의한 후 다음과 같은 연결 목록을 만들었습니다. 목록 연결된 목록 클래스를 사용하여 문자 데이터가 있는 4개의 노드를 삽입합니다. 'a', 'b', 'c', 'd' 그리고 'g' 연결된 목록에서 다음을 사용하여 연결된 목록을 인쇄합니다. 인쇄LL() 메서드 연결 목록 클래스 이후에는 제거 메서드를 사용하여 일부 노드를 제거했습니다. 그런 다음 연결된 목록을 다시 인쇄하면 출력에서 노드가 성공적으로 삭제된 것을 볼 수 있습니다. 그 다음에는 연결된 목록의 크기도 인쇄합니다.
파이썬3
유닉스 대 윈도우
# 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>