인프런 커뮤니티 질문&답변
작성한 질문수
링크드 리스트 원소 찾기 구현 방식 질문드립니다.
해결된 질문
작성
·
15
0
1. 현재 학습 진도
몇 챕터/몇 강을 수강 중이신가요? 2-5
어떤 알고리즘을 학습하고 계신가요? 링크드리스트
여기까지 이해하신 내용은 무엇인가요? 파이썬의 클래스를 이용해서 링크드리스트 구현하기
2. 어려움을 겪는 부분
어느 부분에서 막히셨나요? 원하는 원소찾기 구현
코드의 어떤 로직이 이해가 안 되시나요?
어떤 개념이 헷갈리시나요?
3. 시도해보신 내용
문제 해결을 위해 어떤 시도를 해보셨나요?
원하는 원소를 찾는 것에 파이썬의 list를 사용했습니다.
def get_node(self, index):
cur = self.head
node = []
while cur.next is not None:
node.append(cur.data)
cur = cur.next
return print(node[index])파이썬의 list를 사용해서 원소를 찾아도 될까요?
답변 2
0
안녕하세요 용맹님 좋은 질문 감사합니다!!
우선 결론만 말씀드리면, 동작은 하지만 권장하지 않는 방식입니다!
1. 현재 코드의 문제점
작성하신 코드를 살펴보면 두 가지 이슈가 있어요.
첫째, 마지막 노드가 누락돼요. while cur.next is not None 조건 때문에 마지막 노드에 도달하면 반복문이 끝나버려서, 마지막 노드의 data는 list에 추가되지 않아요. 그래서 while cur is not None 으로 바꾸면 정상 동작할 것 같습니다
둘째, 링크드리스트의 존재 이유를 무색하게 만들어요. 별도의 파이썬 list를 만들어서 모든 데이터를 복사하면, 굳이 링크드리스트를 쓸 이유가 없어지게 됩니다
2. 왜 파이썬 list를 쓰면 안 될까?
기차 비유로 설명을 드려보면, 링크드리스트에서 3번째 칸을 찾는다는 것을 가정해보겠습니다
기차의 모든 칸을 돌아다니면서 각 칸에 뭐가 있는지 전부 종이에 적어두고, 나중에 그 종이를 보고 3번째가 뭐였는지 찾는 거예요.
반면 강의에서 제시하는 방식은: 1번 칸에서 시작해서 "1번, 2번, 3번!" 하고 세 칸만 이동한 다음 멈추는 거예요. 훨씬 효율적인 구현이 됩니다.
3. 강의에서 제시하는 올바른 구현
def get_node(self, index):
cur = self.head
cur_index = 0
while cur_index != index:
cur = cur.next
cur_index += 1
return cur
이 코드의 핵심은 index까지만 이동하고 바로 반환한다는 거예요. 0번째 노드를 찾고 싶으면 head에서 바로 반환하고, 2번째를 찾고 싶으면 딱 두 번만 이동해요.
4. 시간복잡도 관점에서 보면
둘 다 O(n)이긴 한데요, 제시해준 방식은 index가 0이어도 전체를 다 돌아야 하고, 강의 방식은 index가 0이면 바로 반환해요. 그리고 추가 메모리(파이썬 list)를 쓰지 않아서 공간복잡도도 O(1)로 유지됩니다
코딩테스트에서 링크드리스트 문제가 나오면, 보통 "링크드리스트의 특성을 이해하고 있는가"를 평가해요. 별도의 배열로 변환해서 풀면 정답은 맞을 수 있지만, 면접관이 원하는 답은 아닐 수 있습니다
처음에 이런 방식으로 시도해보신 건 자연스러운 사고 흐름이에요! 노드를 따라가면서 카운트하는 패턴이 처음엔 낯설 수 있거든요. 강의의 while문 패턴을 몇 번 직접 손으로 따라가보시면 금방 익숙해지실 거예요. 언제든 편하게 질문주세요!!
0
안녕하세요, 인프런 AI 인턴입니다.
용맹돌맹님이 질문하신 링크드 리스트에서 원하는 원소 찾는 것에 대해 설명드릴게요.
링크드 리스트는 파이썬의 리스트처럼 인덱스를 활용하는 것이 아니라 노드를 순차적으로 탐색하는 방식으로 접근해야 해요. 링크드 리스트는 인덱스를 지원하지 않기 때문에 아래와 같은 방식으로 링크드 리스트를 순회하면서 원하는 인덱스의 원소를 찾는 로직을 구현해야 합니다.
현재 구현하신 코드에서 파이썬의 리스트 node에 데이터를 추가하여 저장하고 인덱스를 사용하였는데, 링크드 리스트의 본질을 유지하려면 이렇게 파이썬의 리스트를 사용하지 않고 직접 인덱스를 탐색해야 합니다.
예를 들어, 다음과 같이 구현할 수 있습니다:
def get_node(self, index):
cur = self.head
current_index = 0
while cur is not None:
if current_index == index:
return cur.data
cur = cur.next
current_index += 1
return None # 만약 원하는 인덱스가 리스트의 범위를 벗어나면 None을 반환합니다.
이 방식에서는 리스트를 사용하지 않고 현재의 노드에서 시작하여 원하는 인덱스까지 노드를 순회하면서 현재 인덱스를 증가시키고 원하는 인덱스에 도달하면 해당 노드의 데이터를 반환합니다.
추가로, 링크드 리스트를 이렇게 탐색하는 방식은 O(n)의 시간 복잡도로 작동한다는 것을 알고 계시면 좋습니다.
계속해서 공부하시다가 막히는 부분이 있으시면 언제든지 질문 주세요!
강의 자료 참고하기도 폴더에서 수업 자료를 확인할 수 있으니 참고하시길 바랍니다.
힘내세요!