Linear Data Structure(선형구조)
저장되는 자료의 전후관계가 1:1 (리스트, 스택, 큐 등)
오늘은 Array 와 Linked List 에 대해서 공부했다. 두가지 다 Linear Data Structure 에 속한다.
Non-Linear Data Structure(비선형구조)
데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프 등). 앞에 저장된 데이터 한 개에 여러 개의 데이터가 뻗어나갈 수 있는 구조로 되어있다.
Array
연속된 같은 크기의 공간에 데이터를 저장한다. 나는 Array를 하나의 길다란 박스가 정해진 크기대로 방처럼 쪼개져있는 형태라고 이해했다. 방의 크기를 정확히 알기 때문에 인덱스도 알 수 있고, 정보를 빠르게 찾을 수 있다.
하지만 새로운 정보를 중간에 삽입하고 싶다면 인덱스 뒷번호인 데이터를 다 밀어줘야하고, 그래서 데이터를 수정하려고하면 오래 걸린다.
장점 (Pros)
- 인덱스를 통한 검색이 용이함.
- 연속적이므로 메모리 관리가 편하다.
- 인덱스 번호만 알면 바로 조회할 수 있기 때문에 조회가 빠르다.
단점 (Cons)
- 크기가 고정되어 있기 때문에 어떤 엘리먼트가 삭제되면, 삭제된 상태를 빈 공간으로 남겨두어야 한다. => 메모리 낭비의 가능성이 있다.
- 데이터의 추가와 삭제가 느리다.
Linked List
하나의 줄로 데이터가 쭉 연결된 형태를 가지고 있고, 주소를 알아야 다른 것을 찾을 수 있다. 다음 데이터를 가르키는 pointer 를 통해서 연결되어 있다. 순서에 따라서 연결되어 있기 때문에 배열과는 다르게 빈 엘리먼트는 허용하지 않는다. 연결해서 포인터가 가르치는 주소를 타고타고 계속 가야 마지막 것을 찾을 수 있기 때문에 조회가 오래걸린다. 간혹 중간에 링크를 잃어버리는 경우에 뒤 쪽을 불러 올 수 없게 되어 쓸모없이 메모리만 차지하고 있는경우가 생길 수 있다.
장점 (Pros)
- 빈틈없는 데이터의 적재
- 데이터의 추가와 삭제가 빠르다.
단점 (Cons)
- 연결해서 타고타고가야 데이터를 찾을 수 있기 때문에 데이터의 조회가 느리다.
