[Python] Linked List

개념

---

링크드 리스트

노드(구조체)가 연결되는 형식으로 데이터를 저장하는 자료구조

배열과의 차이점 : 배열은 논리적으로도 물리적으로도 연속적인 반면, 링크드리스트는 논리적으로 연속적이지만 물리적으로는 비연속적이다.

 

Singly Linked List

- 각 노드가 (value를 담고있는 'data' + 다음 노드를 가리키는 주소 'next')로 구성된다.

- head(맨 앞)에서부터 읽기 시작하여 tail(맨 뒤)까지 읽을 수 있지만 역순으로는 읽을 수 없다.

- 접근 및 탐색은 O(n), 삽입 및 삭제는 O(1)의 시간복잡도를 가진다.

 

Doubly Linked List

- 이전 노드로 갈 수 있는, 즉, 양방향의 노드 이동이 가능한 형태의 링크드리스트이다.

- 각 노드가 (이전 노드를 가리키는 주소 'prev' + value를 담고있는 'data' + 다음 노드를 가리키는 주소 'next')로 구성된다.

- 접근 및 탐색은 O(n), 삽입 및 삭제는 O(1)의 시간복잡도를 가진다.

 

 

 

 

파이썬 - 단일 링크드리스트

---

class Node:
  def __init__(self,data):
    self.data=data
    self.next=None

class SinglyLinkedList:
  def __init__(self): #초기화
    self.head=None

  def append(self,data):
    if not self.head: #self.head가 None이면 아래 실행
      self.head = Node(data)
      return
    last=self.head
    while last.next: #last.next가 None일 때까지 이하 반복
      last = last.next
    last.next=Node(data) #마지막 노드의 last.next에 Node(data)를 할당

  def print_list(self):
    current_node = self.head
    while current_node:
      print(current_node.data, end=" -> ")
      current_node=current_node.next
    print("None")

# 사용 예시
s_list = SinglyLinkedList()
s_list.append(1)
s_list.append(2)
s_list.append(3)
s_list.print_list()

 

 

#실행결과
1 -> 2 -> 3 -> None

 

 

파이썬 - 이중 링크드리스트

---

class Node:
  def __init__(self,data):
    self.data=data
    self.prev=None
    self.next=None

class DoublyLinkedList:
  def __init__(self): #초기화
    self.head=None

  def append(self,data):
    if not self.head: #self.head가 None이면 아래 실행
      self.head = Node(data)
      return
    last=self.head
    while last.next: #last.next가 None일 때까지 이하 반복
      last = last.next
    newNode=Node(data)
    last.next=newNode #마지막 노드의 last.next에 Node(data)를 할당
    newNode.prev=last

  def print_list(self):
    current_node = self.head
    while current_node:
      print(current_node.data, end=" <-> ")
      current_node=current_node.next
    print("None")

# 사용 예시
d_list = DoublyLinkedList()
d_list.append(1)
d_list.append(2)
d_list.append(3)
d_list.print_list()

 

#실행결과
1 <-> 2 <-> 3 <-> None

---

 

 

문제 풀이

---

[문제] 역방향 연결리스트

단일 연결 목록이 주어지면, head 목록을 반전하고 반전된 목록을 반환한다.

 

제약사항:

- 노드 수의 범위 [0,5000]

- 입력과 출력 확인

- 모든 노드 접근해야 함

- Next를 활용해서 순차적으로 순회하고, 방향 변경하여 뒤집는다.

 

==== 함수 정의 ====

class Solution:
  def reverseList(self,head):
    newList = None
    current = head

    while current:
      nextNode = current.next #다음 노드를 미리 저장해둠
      current.next = newList #current가 가리키던 다음 노드를 newList로 변경
      newList = current #현재 노드를 새로운 리스트의 맨 앞에 추가
      current = nextNode #아까 가리키던 노드로 이동해서 계속 반복
      
    # 출력문 추가
    self.printList(newList)  # 여기서 결과 확인 가능

    return newList
    
  def printList(self, node):
    while node:
      print(node.data, end=" -> ")
      node = node.next
    print("None")  # 끝 표시

 

==== 사용 예시 ====

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 연결 리스트 만들기: 1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

sol = Solution()
sol.reverseList(head)

 

 

#출력결과
3 -> 2 -> 1 -> None

 

 

while문 내의 과정을 풀어 정리하자면,

 

[1회차]

1->2->3의 연결 리스트가 있을 때, 초기에는 head가 리스트의 맨 처음 1을 가리킨다.

nextNode에 1.next인 2를 참조하고

current.next 즉, 1의 next에는 None을 참조하게 한다.

newList는 current에 있던 1를 참조하고

current는 nextNode에 있던 2를 참조한다.

 

[2회차]

nextNode는 3을 참조하고

2.next는 1을 참조한다.

newList는 2를 참조하고

current는 3을 참조한다.

 

[3회차]

nextNode는 None을 참조하고

3.next는 2를 참조한다.

newList는 3을 참조하고

current는 None을 참조한다.

 

current가 None이 되므로 반복문은 종료된다.

 

---

 

 

파이썬 문법 알아보기

---

 

__init__

 

파이썬에서 __init__은 클래스의 생성자(constructor) 역할을 해요.
객체를 만들 때 자동으로 호출되어, 객체를 초기화하는 데 사용돼요.

 

예:

class Person:
    def __init__(self, name, age):
        self.name = name  # self.name은 인스턴스 변수
        self.age = age

# 객체 생성
p = Person("Alice", 25)

print(p.name)  # Alice
print(p.age)   # 25

 

여기서 일어나는 일:

1. p = Person("Alice", 25)를 하면,
2. __init__ 함수가 자동 호출돼서 "Alice"와 25가 name과 age에 할당돼요.
3. self는 **자기 자신(생성된 객체)**를 가리켜요.

간단히 말해:
__init__은 객체가 만들어질 때 꼭 해야 할 준비 작업(값 지정, 상태 설정 등)을 처리하는 곳이에요.

 

 

 

 

if not

파이썬에서 if not은 "만약 ~이 아니다" 또는 "거짓이면" 이라고 해석해요.
즉, 조건이 False일 때 실행돼요!

---

🔍 기본 구조

if not 조건:
    # 조건이 False일 때 실행됨

---

✅ 예제 1: 숫자

x = 0

if not x:
    print("x는 0이거나 False입니다.")

👉 x가 0이면 False로 간주되기 때문에 not x는 True가 되고, print()가 실행돼요.

---

✅ 예제 2: 리스트

items = []

if not items:
    print("리스트가 비어있습니다.")

👉 리스트가 비어 있으면 False로 간주되니까, not items는 True!

---

✅ 예제 3: 직접 비교하지 않고 간단하게 쓰기

logged_in = False

if not logged_in:
    print("로그인하지 않았습니다.")

👉 logged_in == False라고 쓰는 대신, if not logged_in이라고 간단하게 표현해요.

---

✨

파이썬에서는 null이라는 키워드는 없지만, 그 역할을 하는 None이 있어요.
그리고 None은 조건문에서 False로 취급돼요! 🙆‍♂️

---

🔎 예제:

x = None

if not x:
    print("x는 None이거나 False로 간주되는 값입니다.")

✅ 결과:

x는 None이거나 False로 간주되는 값입니다.

---

📚 파이썬에서 False로 간주되는 값들 (Falsy values):

다음 값들은 if 문에서 False로 취급돼요:

값 설명

None	null 같은 의미
False	불리언 False
0	정수형 0
0.0	실수형 0
""	빈 문자열
[]	빈 리스트
{}	빈 딕셔너리
set()	빈 세트
()	빈 튜플

---

⚠️ 참고:

None 자체는 False랑 같지는 않아요!

None == False     # False
bool(None) == False  # True

그러니까 None은 값으로는 False가 아니지만,
if not x 같은 조건에서는 False처럼 행동해요. 😄

 

 

 

 

print의 end

 

파이썬의 print() 함수에서 end는 출력 후 줄 바꿈을 대체할 문자(또는 문자열)를 지정하는 옵션이에요!

---

✅ 기본적으로 print()는 이렇게 동작해요:

print("hello")
print("world")

출력:

hello
world

→ 두 줄이 출력돼. 왜냐면 print()는 기본적으로 **출력 후 자동으로 줄 바꿈 (\n)**을 하거든요.

---

✨ 그런데 end를 지정하면?

print("hello", end=" ")
print("world")

출력:

hello world

→ end=" " 덕분에 첫 번째 줄 출력 후 줄 바꿈 대신 공백이 들어갔어요.

---

🔁 너가 준 코드에선:

while current_node:
    print(current_node.data, end=" -> ")
    current_node = current_node.next

여기서 end=" -> "는 각 노드의 데이터를 출력한 후, 줄바꿈 대신 ->를 출력하라는 의미에요.

예시 출력:

1 -> 2 -> 3 -> 4 -> 

---

🎯 요약

end 값 결과 예시 출력

기본값 (\n)	줄 바꿈
end=" "	공백
end=", "	쉼표 + 공백
end=" -> "	화살표 연결