[자료구조] 04. Linked List

안녕하세요? 주니하랑 입니다.

오늘은 자료구조에서 링크드 리스트(연결 리스트)에 대해서 공부 해 보도록 할 것이에요!

제가 작성한 코드가 궁금하시다면? 주니하랑의 깃 허브에 관심을 주세요!

바로 시작 해 보겠습니다!

 

 

---

📌 Linked List ( 연결 List )

---

배열은 순차적으로 연결된 공간에 Data를 나타낸 구조지만, Linked List는 공간이 떨어져 있어도 Data를 가상의 화살표로 연결해서 관리하는 Data의 구조인 것이에요.

본래 C언어에서는 주요한 Data 구조지만, Python은 List Type이 Linked List를 모두 지원한답니다!

 

    📍 Linked List 기본 구조와 용어

• Node(노드) : Data 저장 단위 (Data Value, Pointer)로 구성
• Pointer(포인터) : 각 Node 안에서 다음 혹은 이전의 Node의 주소값 (연결 정보)을 가지고 있는 공간

 

         👉 일반적 Linked List 형태

 

 

    📍 간단한 Linked List

 

          👉 Node 구현

• 보통 Python에서 Linked List 구현시, Python Class 활용
• Python 객체지향 문법 이해 필요

 

 

 

 

    📍 Linked List 장, 단점 (전통적 C언어에서의 배열과 Linked List)

• 장점
  • 미리 Data 공간을 할당하지 않아도 됨
    (배열은 미리 Data 공간을 얼마나 사용할 것인지 할당 필요)
• 단점
  • 연결을 위한 별도 Data 공간 필요하기에 저장 공간 면에서 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하여 접근 속도가 느리다
  • 중간 Data 삭제 시 앞, 뒤 Data의 연결을 재구성해야 하는 부가적 작업 필요

 

    📍 Linked List 복잡한 기능 (Linked List Data 사이 Data 추가)

         👉 Linked List 는 유지 관리에 부가적 구현 필요

출처: wikipedia, https://ko.wikipedia.org/wiki/Linked_list

 

 

 

 

 

 

📌 Doble Linked List (이중 연결 List)

---

• Doble Linked List 기본 구조
  
  • 장점: 양방향 연결로 Node 탐색이 양쪽으로 가능
    앞에 가까운 Node는 앞에서 탐색하고, 뒤에서 가까운 Node는 뒤에서 탐색할 수 있다.

 

출처 : wikipedia, https://ko.wikipedia.org/wiki/Linked_list

 

 

 

---

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글은 주니하랑에게 많은 힘이 됩니다