[알고리즘(algorithm) (2) Arraylist와 Linkedlist] 어떤 알고리즘을 선택해야할까?

알고리즘을 구현하는 것은 자료구조의 탐색으로부터 시작된다.

처리해야할 자료의 형태에 따라 효율적인 알고리즘을 선택해서 구현하는 것이다. 

 

자료구조는 아래와 같이 분류된다.

 

 

자료구조 중에서도 선형구조(1:1)에 해당하는 Array와 Linkedlist에 대해 알아보자. 

 

건물에 비유하자면, Arraylist는 아파트의 한 층이 연결되어있는 구조이고

Linkedlist는 층이 다른 여러 집들이 연결되어있는 구조이다.

 

 

출처 : 생활코딩

 

아래 그림과 같이

Arraylist는 한층에 모여있는 구조이기 때문에 데이터를 조회할때는 빠르지만,

추가나 삭제를 할때에는 전체구조를 변형해야하기 때문에 느리고 어렵다. 

 

Linkedlist는 산발적으로 연결이 되어있기 때문에 데이터를 조회하려면

head에서 시작하여 연결고리를 따라가야만 값을 찾을 수 있어서 느리지만,

각각의 데이터에 접근해서 그 부분만 추가하거나 삭제할 수 있기 때문에 

빠르고 효율적이다. 

 

Arraylist와 Linkedlist의 trade-off (출처 : 생활코딩)

 

 

 

Arraylist와 Linkedlist의 차이는 알겠는데,

array에만 익숙한 우리는 Linkedlist가 너무 막연하게 느껴진다.

 

Linkedlist를 활용하여 어떻게 데이터를 추가 또는 삭제하고 조회할까?

간단한 예시를 통해 정리해보자.

 

1. 추가

Vertex pre = head #head 에서 부터 시작

for (k = 0; k < i-1; k++) # K번째에 추가하고 싶다

  pre = pre.next # next node로 이동

Vertex aft = pre.next # 추가될 자리의 node (뒤로가야할 node)

Vertex vtx = new Vertex(v) # 새로운 node 생성(연결X)

vtx.next = aft # 새로운 node의 next를 aft로 지정

pre.next = vtx # K번째 node의 next를 새노드로 지정하여 연결

 

2. 삭제

if empty, do nothing

Vertex pre = head # head에서 시작

for (k = 0; k < i-1; k++) #K번째를 삭제하고 싶다

  pre = pre.next # 삭제할 노드로 이동

Vertex del = pre.next, aft = del.next
# 삭제할 node를 지정하고, 삭제할 node 뒷자리(연결예정node) 지정

pre.next = aft // bypass del
# pre.next = pre.next.next 와 같음
# 삭제할 node의 연결을 끊어 그 다음 노드로 연결

delete del # 삭제할 node 삭제 실행

3. 조회

if empty, return NOT_FOUND

index = 0, temp = head # index 0부터, head 부터 시작

while (temp.item != v) # 찾고자하는 value를 v로 정의

  index++, temp = temp.next
# 반복문이 돌때마다 index += 1 해주고, next로 이동

  if temp == null # 끝 node로 이동해도 값이 없으면

    return NOT_FOUND # 찾지 못했음 반환

return index # 찾는 v값이 있으면 index 반환

 

마치 기차를 타고 옆칸으로 이동하는 것과 같은 Linkedlist 의 기본원리를 활용하여

다양한 자료구조 처리에 녹여내보자🤔