Array(배열)과 Linked List(연결 리스트)

Array 와 Linked List 둘다 자료구조의 형태 중 하나이다.

Array(배열)

Array(배열) 는 입력된 데이터들이 연속적인 데이터 공간에서 순서데로 데이터를 저장하는 자료 구조이다.

장단점

array는 index로 탐색을 쉽게 할 수 있지만 데이터를 삽입하거나 삭제를 할 때 다른 데이터를 순서대로 모두 이동을 시키기 때문에 연산비용이 많이듭니다.

• 장점
  • indexing을 통한 빠른 접근이 가능하다.
• 단점
  • 데이터 삽입 삭제가 오래 걸린다.
  • 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생한다.

 

Linked List(연결 리스트)

Linked List(연결 리스트) 는 입력된 데이터들이 비 연속적인 데이터 공간에서 순서데로 데이터를 저장하는 자료 구조이다.

그리고 그 데이터가 Linked(연결) 되어 있다. 다른 말로 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이다.

첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다.

장단점

linked list는 index가 없기 때문에 head에서부터 순차적으로 탐색해야 해서 탐색은 느리지만, 삽입 삭제 연산을 할 때 노드를 끊고 연결만 해주면 되기 때문에 삽입삭제 연산은 빠릅니다.

• 장점
  • 노드가 연결된 구조이기 때문에 데이터 삽입, 삭제에 용이하다.
• 단점
  • Linked List는 데이터를 저장하는 공간 + 다음 데이터를 연결하기 위한 공간이 필요하기 때문에 array에 비해 공간을 더 많이 차지한다.
  • array와 다르게 데이터를 접근할 때 0번째부터 순차적으로 접근해야 하니, 데이터를 접근할때는 array보다 느리다.