visualgo.net을 통해서 Linked list가 어떻게 동작하는지 살펴보는 시간이다..
Linked list를 시각화해서 보여주는 페이지로 이동한다.
노드 다음 노드 다음 노드.. 이런식으로 연결되어 있는 것을 시각적으로 확인할 수 있다.
85를 헤드에 넣어보자.
그럼 이런 그림을 볼 수 있다!
85를 헤드에 추가하는 과정을 하나하나 확인해보자.
코드를 보자. Vertex vtx = new Vertex(v)
Vertex라는 객체를 new로 만들었다.
또한 Vertex라는 객체를 생성할 때, 'v'라는 값을 매개변수로 줬다.
우리가 방금 입력한 85라는 숫자가 저 v의 값으로 들어가서, 85라는 값을 가지고 있는 노드가 만들어졌다.
그 노드의 이름은 vtx라고 보면 된다.
저 vtx라는 노드가 그림에서 동그라미 85에 해당된다고 보면 된다.
List에서는 head라는 변수가 있다.
누가 그 리스트의 시작인가를 지정하는 변수이다!
현재 head변수가 가르키고 있는 노드는 동그라미 22이다!
자아.. 우리가 방금 만든 85라는 노드에는 .next라는 변수가 내부적으로 존재하는데, 그 변수가 기존의 첫번째 노드를 가르키게 한다면?
85라는 노드의 다음 노드가 '현재 head가 가르키고 있는 노드인 22'가 된다.
계속 진행해서..
이런 과정이다.
간단하지만 아주 중요한 것이다!
linkedlist에서 노드와 노드는 next로 연결되어 있다는 것을 기억하자.
정리하자면,
1. 노드를 생성한다.
2. 새로 생성한 노드에 next값으로 현재 이 리스트의 첫번째 노드를 지정한다.
3. 내가 생성한 노드를 이 리스트의 시작이 되는 노드로 만들기 위해서 head = vts
노드를 첫번째 위치에 추가하는 것을 살펴보았다
그럼 이 중간 어디에 노드를 추가하면 어떻게 되는가?
조금 더 복잡하다.
중간에 추가.. i=3자리에 90이라는 값을 추가해주었다.
순서.
1. pre라는 노드를 헤드로 지정했다.
2. 반복문. for(k=0; k<i-1;k++) 내가 아까 i를 3으로 했다. 그러므로 k=0,1인 경우에 pre = pre.next한다.
이 pre는 추가할 노드의 '바로 앞'에 위치해야 하므로.. i-1이라고 써줘야 하겠지! ㅎ.ㅎ
k=0일 때 -> pre라는 것은 더이상 head자리의 22에 해당하지 않고, pre = pre.next이다. 즉 다음 것이 pre이다.
(참고: for(k=0; k<i-1; k++)도 좋고, while(--k!=0)도 좋다.
강의를 보면 i가 아니라 k로 변수 이름이 설정되어 있더라. 예전 visualgo에서는 k로 했나 보다. 아무튼.
내가 앞에서 i=3으로 지정해서 0,1,2,3의 3번째 노드(인덱스3) 에 값을 추가한건데,
while(--k!=0)에서의 k를 이용해서 3번째 노드에 값을 추가하려면 어떻게 해야 할까?
pre는 내가 추가할 노드의 위치의 바로 앞에 위치해야 하므로.. 3번째 인덱스에 추가하려 했으면 pre는 두번째 인덱스에 위치해야 한다. 그러므로 0->1 한번, 1->2 두번! 이렇게 두번 pre = pre.next를 수행해야 한다.
그러므로 k=3이면 된다. k=2,1인 조건에서 반복문을 수행한다. 그렇게 두 번 진행하게 된다.
(인덱스 3자리에 추가할 거니까, k=3으로 초기에 설정하고, 적절한 실행 횟수를 위해 --k로 세팅했다.
3. 반복문 속 k=1인 경우를 계속 진행한다. pre = pre.next 한번 더 실행하자는 것이다.
이제 k<i-1의 조건을 만족하지 않으므로, 반복문을 빠져나온다.
4. aft라는 노드 = pre.next라고 하자. pre의 다음 노드를 aft라고 이름 붙였다.
5. Vertex vtx = new Vertex(v)
vtx라는 새로운 노드를 생성했다!
우리가 추가하려는 노드 자리의 앞뒤에 존재하는 노드의 래퍼런스값을 찾아서 연결해줘야 한다.
6. vtx.next = aft
vtx의 다음 노드는 aft라고 연결한다.
7. pre.next = vtx
pre의 다음 노드는 vtx라고 연결한다.
그럼 Linked List에서 노드를 중간에 추가하기 완료!
Linked List에서는 앞 뒤의 관계 정보만 바꿔주면 데이터의 삭제나 추가가 이루어진다.
반면 Array List에서는 중간에 추가하면 싹 다 밀어서 자리를 만들어야 하기 때문에 느리다.
이런 이유로 Linked List가 빠르다는 것이다.
'자료구조 + 알고리즘' 카테고리의 다른 글
| [자료구조] Linked list 데이터 조회 [VisuAlgo.net] (0) | 2020.04.02 |
|---|---|
| [자료구조] Linked list 데이터 삭제 [VisuAlgo.net] (0) | 2020.04.02 |
| [자료구조] Linked list의 구조 (0) | 2020.03.28 |
| [자료구조] 원소를 무한히 저장하는 ArrayList 구현하기 [JAVA] (0) | 2020.03.28 |
| [자료구조] ArrayList 구현 - size, indexOf [Java] (0) | 2020.03.18 |