[자료구조] Linked list 데이터 조회 [VisuAlgo.net]

---

두 가지 데이터 조회 방법이 있다.

1. 77이라는 값을 가진 노드를 조회하겠다.

2. 네번째 자리 (인덱스3)에 있는 값을 가져오고 싶다.

순서대로 알아보자.

 

 

---

77이라는 값을 가진 노드를 조회하겠다. ( v = 77 이라고 visualgo.net에서 설정하고 간다. )

간단하다.

index = 0, temp = head

while (temp.item !=v)

  index++, temp = temp.next

  if temp == null

    return NOT_FOUND

그냥 코드 읽어보면 다 알거다.

---

네번째 노드의 데이터를 조회하고 싶다면 어떻게 할까?

 

첫번째 노드로 접속하고, 넥스트하고 인덱스 카운트, 넥스트하고 인덱스 카운트.. 하면서

해당 인덱스로 왔을 때, 그 노드에 있는 값을 출력해주면 된다.

'물어서 물어서 차례로 이동을 해야 한다.'

 

반면, ArrayList에서는 ArrayList가 가진 인덱스의 특징을 강력하게 활용할 수 있다.

'그 주소로 바로, 직접 접근할 수 있다' -> 속도가 굉장히 빠르게 데이터를 가져올 수 있다.

 

그래서 ArrayLists는 인덱스 조회로 값을 가져올 때, LinkedList와 비교도 안되게 빠르다.

 

그래서 우리가 ArrayList와 LinkedList를 각 사용 목적에 맞게 잘 사용을 해줘야 한다.

각각의 장단점을 조합해서 우리가 필요한 자료구조를 만들어 낼 수도 있겠다. (또다른 단점이 생길 수 있지만)

 

 

이렇게 뭐든지 Trade off가 존재한다.

 

 

ㅇ추가,삭제는 LinkedList

ㅇ인덱스 조회는 ArrayList

 

ㅇLinkedLIst는 포인터,참조값으로 각각의 노드가 연결되어있기 때문에, 노드를 무한대로 키울 수 있다. List의 크기가 확정적이지가 않다. (메모리가 허용하는 한에서..)

ㅇArrayList에서는 배열이라고 하는 아주 융통성없는 자료구조를 이용하기 때문에, 배열이 갖고있는 크기를 넘어서면 에러가 발생한다. 혹은 배열의 크기를 과다하게 지정할 경우, 공간의 낭비를 만들 수 있다.

 

 

출처

https://programmers.co.kr/learn/courses/17/lessons/805