[D+22] Linked List

 

 

국비지원 D+22

-  Linked List -

 

---

 

Linked List

• 정의

기존에 우리가 배운 배열은 연결되어 붙어있는 자료구조로 접근하기좋으며, 변경되지 않는 고정적인 데이터에 사용이 용이한 장점을 가지고 있다.

그러나 배열에도 단점이 존재하는데 바로 중간에 데이터를 빼거나 추가할 경우 연산이나 구조가 변경되기 쉬우며 배열긔 크기가 고정적인 특징으로 인해 추후에 얼마나 많은 양의 데이터가 들어올지 몰라 사이즈를 크게잡아 메모리가 낭비될 염려가 있었다.

 

이러한 배열의 문제점을 극복하기 위해 바로 Linked List가 등장하게 되었다.

 

• 구조

Linked List는 Data와 다음 노드를 참조하는 참고값을 담고있는 노드로 구성되어 있으며, 데이터를 추가할때 마다 노드가 추가되며 동시에 이전 노드가 새로추가된 노드의 위치정보를 노드안에 담는 형식으로 되어있다.

 

• 장/단점

장점)

- 데이터를 중간에 추가하거나 빼는데 편리하다.

- 메모리가 낭비되지 않는다.

 

단점)

- 접근시에 소스코드가 복잡해져 코드의 복잡도가 상승한다. => 연산의 횟수가 증가

- 메모리 어노테이션시 속도가 느리다. => new 연산이 많아지면 속도가 느려진다.