자료구조란?

• 데이터를 조직적으로 관리하여 구조적으로 표현하는 방식
• 7가지의 기본 자료구조
  • 배열(Array)
  • 연속 리스트(Contiguous list)
  • 연결 리스트(Linked list)
  • 스택(Stack)
  • 큐(Queue)
  • 트리(Tree)
  • 그래프(Graph)
• 자료구조의 연산 : 읽기 검색 삽입 삭제

배열(Array)

• 단순한 데이터 원소들의 리스트
• 크기 : 배열에 데이터 원소가 얼마나 들어있는지
• 인덱스 : 특정 데이터가 배열의 어디에 있는지 알려주는 숫자. 인덱스는 0부터 시작.

연속리스트(Contiguous list)

• 배열과 같이 인덱스를 통해 Value에 접근하며, 배열처럼 연속적인 기억 장소에 데이터가 저장되는 자료구조이다.
• 배열과 연속 리스트의 차이점

  • 삽입 시 차이점

    배열은 데이터 삽입시 인덱스의 데이터를 덮어쓰는 형태로 삽입한다.

    연속리스트에서는 삽입 되어지는 데이터를 한 칸씩 뒤로 밀고 해당 자리에 삽입한다.

  • 삭제 시 차이점

    배열은 데이터 삭제시 해당 데이터 인덱스는 메모리가 비어있는 상태가 된다.

    연속리스트에서는 데이터가 삭제되고 뒤에 있는 데이터들이 앞칸으로 한 칸씩 전진하며 채워진다.

연결리스트(Linked list)

• 일렬로 연결된 데이터를 저장할 때 사용

• 연속 리스트와 다르게 가장 큰 특징은 메모리의 각 부분에 다음 순서의 데이터를 가리키는 포인터(Pointer)가 존재한다는 것이다.

• 노드(Node) : 데이터와 포인터를 합쳐서 노드라고 말한다

• 단순히 노드의 point가 가리키는 것을 바꾸는 것만으로 데이터의 추가, 삽입 삭제가 가능하다.

  예컨데 앞서 말한 Contiguous List에서는 데이터를 중간에 넣을 시에 뒷 칸의 데이터를 모두 뒤로 미뤄야 했지만 연결리스트는 그냥 서로의 연결 고리를 끊고 새로 들어온 데이터에 연결 고리를 묶어주면 되는 것이다.

• 단 방향 리스트

오직 다음 주소만 어디있는지 알고있기 때문에 검색을 할 때는 맨 앞에 있는 노드부터 하나씩 노드를 이동하면서 검색해야한다

삽입:삽입하고 싶은 위치에 노드를 위치시키고 전 노드의 주소를 삽입노드로 삽입노드는 다음 주소를 가르키게한다