연결 리스트

연결 리스트에 공부하기에 앞서

 

선형 자료 구조에 대해 알 필요가 있습니다

 

1. 어레이

2. 연결 리스트

3. 스택

4. 큐

...기타등등

 

스택과 큐는 나중에 알아보기로 하고

일단 어레이와 연결 리스트에 대해 봅시다

---

 

어레이

어레이는 기차입니다

앞이 0번이고 기차의 길이 N은 항상 정해져있습니다

 

JAVA에서 우리는

int[] arr = new int[n]; 이렇게 쉽게 이용이 가능합니다

arr 기차의 길이는 n이고

각 객실에는 int 가 탑승한다는 뜻입니다

 

K번 객실에 탄 사람?

arr[K-1] 로 바로 호출이 가능합니다 

---

 

연결 리스트의 기본 '노드'

어레이는 하나의 객실이 기본이라면

연결 리스트는 '노드'가 기본이 됩니다

 

노드는 하나의 데이터와 하나의 포인터로 이루어져있습니다

 

데이터에는 데이터가 담기고

포인터는 이 노드 다음에 어떤 노드가 오는지에 대한 정보가 들어있습니다

이 포인터를 연결시켜 순서를 부여하면

연결 리스트가 됩니다

 

특히 연결 리스트의 첫번째 노드를 해드 라고 부르고

마지막 노드를 테일 이라고 부릅니다

 

마지막 노드의 다음에는 노드가 없으므로

테일의 포인터 부분은 null이 됩니다

 

4번째 어레이를 조사하려면 바로 한번에 arr[4-1]를 하면 되지만

4번째 연결 리스트를 조사하려면 0 > 1 > 2 > 3 이렇게 3번의 과정을 거쳐야만 가능하는

이런 단점이 있습니다

 

---

연결 리스트의 장점은

수정이 쉽고 빠르다 입니다

 

어레이에 새로운 데이터를 중간 k번째에 추가하기 위해서는

n+1 길이 만큼의 새로운 어레이를 만들어서

0~k-1까지 데이터를 입력을 하고

k번째 새 데이터를 추가 한 이후

k+1~n+1까지의 데이터를 한칸씩 옮겨야합니다

 

하지만 연결 리스트는 다릅니다

 

새 데이터 추가 전

새 데이터 추가 방법

단순히 포인터의 방향을 바꾸는 것 만으로도

내용 수정이 가능하다는

장점이 있습니다