[파이썬 | 자료구조] 링크드리스트(Linked List)

안녕하세요~ ☺️

지난 시간에는 반드시 알아 두어야 할 자료구조 스택(Stack)를 배웠습니다.

이번 시간에는 대표적인 데이터구조 링크 드리스트(Linked List)를 배워보겠습니다.

 

링크드 리스트의 구조

링크드리스트는 말 그대로 연결리스트이다.

떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.

링크드리스트는 노드와 포인터로 이루어져있습니다.

본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원

 

즉 이러한 형태 한공간(Node)을 두공간(Data와 Next)으로 분리시켜 데이터를 담을 수 있는 Data공간과

다음 노드를 가리킬 수 있는 Next공간을 연결시킨 형태라고 볼 수 있다..!

여기서 다음 노드를 가리 킬 Node가 없으면 마지막 Node의 Next를 None으로 초기화시키면 된다.

 

이제 파이썬에서 링크드리스트(Linked List)를 한번 구현해 보기전에

링크드리스트의 장단점을 한번 살펴볼까요?!

링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)

• 장점
  • 미리 데이터 공간을 미리 할당하지 않아도 됨
    • 배열은 미리 데이터 공간을 할당 해야 함
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

이를 그림으로 나타내 보면 이러한 구조가 나옵니다. 맨앞부분이 head가 될 것이고요!

자 여기서 데이터를 한번 추가해 보겠습니다.

처음에 12를 추가하고 이어서 99, 37을 추가했습니다. 잘 연결되어있는 걸 확인 할 수 있죠??!

이러한 형태로 리스트연결이 되었다고 볼 수 가 있습니다.

 

자 그럼 연결리스트에 데이터를 추가했다면 삭제도 해야겠죠??!

삭제를 위한 delete함수도 한번 구현해 보겠습니다.

주석을 달아놓았으니 곰곰히 생각해보시면서 이해하시길 바랍니다😊

테스트를 해보겠습니다..!

12 ->99-> 37 로 연결된 연결리스트에서 delete함수를 이용해 삭제를 해보았습니다. 45라는 데이터를 삭제를 했을 시 반응이 없죠??

해당 연결리스트에 45라는 데이터를 찾지 못해 아무 동작도 하지않고 리턴을 한 것이죠. 그 후 99라는 데이터를 삭제 했을 시 연결리스트에 

들어있던 99라는 데이터가 삭제가 되었고 나머지 데이터들이 잘 연결되었음을 알 수 있습니다.

 

자 이렇게 연결리스트 추가/삭제 까지 알아 보았는데 여기서 특정노드를 찾는 search_node함수까지 구현해봅시다.

찾는 함수는 생각보다 간단하죠??

자 다시 한번 테스트 해보겠습니다.

조회한 데이터도 잘 나오는 것으로 보입니다.

 

linked_list라는 변수를 Node를 관리해나가는 NodeMgmt()함수를 이용해 정의했습니다.

add

함수와 delete함수, search_node함수, desc함수를 정의했습니다.

 

add 함수는 리스트변수에 노드가 존재하지않으면 새노드를 만들고 노드가 존재하면 노드를 next로 연결하게 구현했습니다.

delete 함수는 리스트변수에 삭제할 데이터가 첫번째이면 head를 다음 노드로 옮긴 후 삭제하고 삭제할 데이터가 첫번째 이후라면 삭제할 데이터의 전노드를 삭제할 데이터의 후노드로 연결 후 삭제하게 구현했습니다.

search_node 함수는 찾고자하는 노드가 있을 때 까지 다음 노드를 가르키게 구현했습니다.

desc 함수는 현재 가진 데이터를 보여줄 수 있게 구현했습니다.

 

자 이렇게 대표적인 데이터구조 링크 드리스트(Linked List)를 배워보았습니다.

다음으로는 더블 링크드리스트 (Double Linked List)를 알아보겠습니다.

읽어주셔서 감사합니다 :)