24.01.17 선형 자료 구조 1

1. 선형 자료 구조

    - 요소가 일렬로 나열되어 있는 자료 구조를 말한다

 

  1) 연결 리스트

       - 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조

       - 삽입과 삭제가 O(1) 이 걸리며 탐색에는 O(n) 이 걸린다

       - 아래 그림처럼 prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결리스트

       - 맨 앞에 있는 노드를 헤드(head) 라고한다

        * 싱글 연결 리스트 : next 포인터만 가짐

        * 이중 연결 리스트 : next 포인터와 prev 포인터를 가짐

        * 원형 이중 연결 리스트 : 이중 연결리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것

 

  2) 배열

       - 같은 타입의 변수들로 이루어져있고, 크기가 정해져있으며, 인접한 메모리 위치에 있는 데이터를

         모아놓은 집합으로 중복을 허용하고 순서가 있다

       - 정적 배열을 기반으로 공부

       - 탐색에 O(1) 이 되어 랜덤 접근이 가능하다

       - 삽입과 삭제에는 O(n) 이 걸린다. 따라서 데이터 추가와 삭제를 많이 하는 것은 연결리스트,

         탐색을 많이 하는 것은 배열로 하는것이 좋다

       - 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용

 

     (1) 랜덤 접근과 순차적 접근

           - 직접 접근이라고 하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의

             인덱스에 해당하는 데이터에 접근할 수 있는 기능

           - 랜덤 접근은 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대 개념

    

     (2) 배열과 연결 리스트 비교

           - 배열은 상자를 순서대로 나열한 데이터 구조이며 몇 번째 상자인지만 알면 해당 상자의 요소를 끄집어 낼 수 있다

           - 연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조이며, 상자 안의 요소를 알기 위해서는 하나씩

             상자 내부를 확인해 봐야 한다

           - 아래 그림에서 유추할 수 있듯이 탐색은 배열이 빠르고 연결 리스트는 느림

           - 배열의 경우 그저 상자 위에 있는 요소를 탐색하면 되는 반면, 연결 리스트는 상자를 열어야 하고

             주어진 선을 기반으로 순차적으로 열여야 함

           - 데이터 추가 삭제는 연결 리스트가 더 빠르고 배열은 느림

           - 배열은 모든 상자를 앞으로 옮겨야 추가가 가능하지만, 연결 리스트는 선으 ㄹ바꿔서 연결 해주기만

             하면 되기 때문