1. 링크드리스트란(Linked List)?
Key Ponint 💡
링크드 리스트란?
- 연결 리스트 라고도 함
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 배열은 미리 특정한 연결된 공간을 예약을 하고 거기에 데이터를 쓰고 읽는 구조
- 링크드 리스트는 미리 예약을 하지 않고 필요할 때마다 데이터를 더 추가하는 구조
- 배열의 단점을 극복한 자료구조가
링크드 리스트라고 한다.- 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
- 링크드리스트는 데이터와 데이터를 가리키는 주소를 한번에 담고 있고 이것을 하나의 데이터로 부른다.
- 이러한
데이터+데이터의 주소=노드(Node)- 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원
2. 링크드 리스트 기본 구조와 용어
Key Ponint 💡
링크드 리스트 구조
- 노드(Node) : 데이터 저장 단위(데이터 값, 포인터)로 구성
- 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
- 즉, 다음 데이터를 가리키는 주소값
- 일반적인 링크드 리스트 형태
(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)
- 노드 : 3개
- 포인터 : 3개 (화살표)
3. 링크드 리스트 예시
- 보통 파이썬에서는 링크드 리스트 구현시, 파이썬 클래스를 활용한다.
- 파이썬 객체지향 문법 이해 필요
- 참고 : https://www.fun-coding.org/PL&OOP1-3.html
- 10 ~ 12
Key Ponint 💡
node를 만들기 위해서는 class를 사용하여야 한다.
why? 하나의 노드에는 데이터와 데이터 주소를 저장해야 하기 때문에, 그에 맞는 구조는 클래스가 수월하다.
class Node:
# 객체를 만들때, self가 항상 앞에 붙는다.
# 하지만, 인자로 사용x
def __init__(self, data, next=None): # next=None 두 번째 인자를 넣으면 주소로 인지하고
self.data = data
self.next = next # 주소값을 여기에 넣어준다.
# Node에 인자르 두개 써 넣으면 주소도 입력하고, 그렇지 않으면 None으로 받는다
- node와 node 연결하기(포인터 활용)
node1=Node(1) # next=None으로 디폴트 값이므로 인자는 하나만 넣어도 된다.
node2=Node(2)
node1.next=node2 # 노드와 노드의 연결 (next로 연결)
head=node1 # 가장 맨 앞의 노드
print(head) # <__main__.Node object at 0x00000245867501C0> -> node1의 주소값
print(node1.next) # <__main__.Node object at 0x0000024586750AC0> -> node2의 주소값
print(node2.next) # None
Key Ponint 💡
init의 이해
- 컨스트럭터(생성자)라고 불리는 초기화를 위한 함수(메서드)이다.
- 인스턴스화를 실시할 때, 반드시 처음에 호출되는 특수한 함수
- 오브젝트 생성(인스턴스를 생성)과 관련하여 데이터의 초기를 실시하는 함수이다.
- init()은 반드시 첫 번째 인수로 self를 지정해야한다.
- self에는 인스턴스 자체가 전달되어 있다.
- 이로 인해, 최과 메소드 내에 인스턴스 변수를 작성하거나, 참고하는 것이 가능해진다.
- 클래스를 생성할 때에 지정한 인수는 초기화 메소드의 2 번째부터 작성해 나가면 된다.
class SomeClass: def __init__(self,something):#constructor self.something = something4. 다양한 링크드 리스트 구조
Key Ponint 💡
더블 링크드 리스트 기본 구조 - 이중 연결 리스트라고도 한다.
장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
이게 마즐까?