[ 알고리즘 ] 연결리스트(Linked List) 삽입/조회(그림으로 이해하기)

 

연결리스트(Linked List) 삽입/조회(그림으로 이해하기)

■ 연결 리스트 개념 이해

 

연결리스트는 여기저기 흩어져있는 데이터를 다룹니다.

일렬로 데이터를 처리하는 배열과 큐와는 완전히 다른 개념입니다.

 

위 그림처럼 데이터가 서로 떨어져 있을 수 있는 이유는 동적 메모리를 할당하기 때문입니다. 

 

연결리스트에서 메모리에 있는 자료형을 노드라고 부릅니다.

데이터를 저장하는 장소와 다음 데이터를 가리키는 포인터 변수로 구성되어 있습니다.

 

처음노드를 가리키는 노드는 없어서 head라고 부릅니다. 

마지막노드는 가리켜야할 다음 데이터가 없어서 null 포인터를 가지고 있습니다. 

 

 

 

 

 

---

■ 연결 리스트 삽입

 

- 15와 30 사이에 20를 삽입하고 싶으면 포인터 2개만 변경해주면 됩니다. 

- 15 데이터의 포인터 변수는 20노드를 가리키고, 20데이터의 포인터 변수는 30를 가리키도록 변경합니다.

- 이미 삽입할 위치(각 노드의 주소)를 알고 있다는 가정하여 O(1) 걸립니다.

---

■ 연결 리스트 조회

 

 

색인 개념이 없기 때문에 특정 데이터를 검색하려면 첫 번째 노드(헤드,head)부터 찾아야합니다. 

그래서 O(n)이 걸립니다.

25가 들어갈 위치를 찾아보겠습니다. 현재 노드는 15로 찾는 값보다 작습니다. 이어서 다음 노드를 검색합니다. 

 

 

현재 노드는 20입니다. 여전히 25보다 작기 때문에 다음을 검색합니다.

현재 노드는 30입니다. 25보다 큰 수이고, 전 노드(20)인 점을 고려하면 20과 30 사이에 25를 삽입하면 됩니다.

 

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------