[04-2] 연결 리스트의 활용

연결 리스트는 앞서 정리한대로 활용성이 매우 뛰어나다.

분명 용량도 크고, 시간도 오래걸리고 복잡도도 크지만 쓰는 데에는 다 이유가 있다.

 

그래서 활용할 수 있는 Operations들을 정리해보고 구현해보자.

 

- get()

특정 인덱스의 값을 가져온다.

어떻게 해야할까? 1번의 인덱스,,n번의 인덱스 값을 가져오려면?

앞서 든 예시로 보자. 우리반에 18번애 이름을 알고 싶으면? 1번부터 물어서...18번까지 찾으면 된다.

그러면 1번(head)에 접근해서 18번까지 쭉 간다음에 value를 return 하면 되겠지?

즉 n번까지 해야하니까 시간 복잡도는 O(n)이 된다.

 

-insert_at()

특정 위치에 값을 넣고 싶다

어떻게 해야할까? 우선 넣고 싶은 위치(idx)와 값(value)를 받아야겠지.

그러면 우선 연결이 끊기기 전에 내가 넣을 값이 그 다음 값의 주소를 기억했다가 사이에 넣으면 된다!

insert 과정

즉 이런 순서로 연결하면 되는것이다.

 

-insert_back()

뒤에 계속해서 연결하고 싶다면 어떻게 해야할까?

계속 append를 활용해서 1번부터 n번까지 쭉쭉 타고 들어가야할까?

O(n)으로?

더 쉬운 방법이 있지 않을까? 바로 tail을 쓰는 것이다. 사고를 확장시켜보자.

꼭 head만 있어야 하나? tail(끝)이 있으면 안될까? 그럴리가! tail을 만들어 표현하면 훨씬 쉬워진다.

tail의 구조

이처럼 tail을 설정해두고

node = Node(4)
self.tail.next = node #현재 tail의 다음을 새로운 노드(4)로 연결하겠다!
self.tail = self.tail.next #tail을 현재 tail 다음(즉 맨끝)으로 변경하겠다!

 

이렇게 하면 아주 쉽게 되겠지?

 

 

연결 리스트는 코딩 테스트의 단골 문제는 아니다.

하지만 앞서 말했듯이 tree, graph의 기초가 되기 때문에 잘 이해할 필요가 있다.

 

연결 리스트는 어떻게 써야하는가?

1. 자유자재로 구현할 줄 알아야 한다. 선형 자료구조에 활용하거나, 중간에 내가 원하는 데이터를 추가 및 삭제할 줄 알아야한다.

2. 트리나 그래프에 활용할 수 있어야 한다.

 

코드의 구조를 보면 사실 쉽게 이해하긴 어렵다.

이 self가 뭔지~ 저게 뭔지 헷갈리고 어려웠거든.

 

하지만 그럴때일수록 천천히라도 코드를 하나씩 떼어가면서 이해해보는게 필요하다.

 

총평

 

코테를 준비하면서 '아 리스트로 할 수 있을 거 같은데.. 슬라이스를 해야하나.. 어쩌지?' 라는 생각이 들었다면? Linked List를 쓰면 된다