Algorithm
List

리스트 (List)

Array List

  • Array
  • Dynamic array

Linked List

  • Node

배열이란?

배열은 선언시에 size를 정하여 해당 size만큼의 연속된 메모리를 할당 받아 data를 연속적 / 순차적으로 저장하는 자료구조이다.

int arr = [5] = {3,7,4,2,6}

위의 예시에서는 배열의 size를 5로 정했기 때문에 int형 데이털 4byte 5개를 저장할 메모리 공간인 20 Byte를 미리 할당을 받습니다. 이처럼 고정된 size를 갖게 되기 때문에 static array라고 부르기도 한다.

Random access

메모리에 저장된 데이터에 접근하려면 주소값을 알아야 한다. 배열변수는 자신이 할당받은 메모리의 첫 번재 주소값을 가리킨다. 배열은 연속적 / 순차적으로 저장되어 있기 때문에 첫 주소값만 알고 있다면 어떤 index에도 즉시 접근이 가능하다. 이를 direct access or random access라고 부른다. 첫 번째 데이터가 저장된 주소값이 Ox4AF55라면 2번 째 데이터는 0x4AF55 + 4(n-1)에 저장되어 있을 겁니다. 아무리 긴 배열이더라도 한번의 연산으로 원하는 데이터에 바로 접근할 수 있다. -> Big O(1) 시간 복잡도를 가진다.

그러나 Linked list는 메모리상에서 연속적 / 순차적으로 저장되어 있지 않기 때문에 random access는 불가능하다. n번 째 데이터에 접근하기 위해서는 array는 1번의 연산만 해도 되지만

O(1) linked list는 n 번의 연산을 해야하기 때문에 시간복잡도는 O(n)이 된다.

Static array의 한계

데이터의 갯수가 정해져 있는 경우에는 static array를 사용하는 것이 매우 효율적이다. 하지만 선언시에 정한 size보다 더 많은 데이터를 저장해야 하는 경우 공간이 남아있지 않아서 문제가 발생할 수 있다. 그렇다고 매번 크기가 큰 배열을 선언한다면 그만큼 메모리 비효율이 발생. 이런 문제점들을 해결하는 것이 Dynamic Array이다.

동적 배열 이란? (Dynamic Array)

선언 이후에 size를 변경할 수 없는 정적배열과 다르게 동적배열은 size를 늘릴 수 있다. 할당받은 배열보다 더 큰 size를 동적으로 할당 받는 것을 resizing(리사이징)이라고 한다. 리사이징 과정은 배열 저장 공간을 다시 할당받고 이전에 할당 받은 값들을 그대로 복사해서 다시 저장한다. 그리고 다시 새로운 값들을 저장하는데 이 때 Big O(n)이다.

동적 배열은 배열의 크기를 변경할 수 있는 배열이다. fixed-size인 static array의 한계점을 보안하고자 고안되었다. 동적배열에 데이터를 계속 추가하다가 기존에 할당된 size를 초과하게 되면, size를 늘린 배열을 새로 선언하고 그곳으로 모든 데이터를 옮긴다. 그리고 기존의 배열은 메모리에서 삭제합니다. 이 과정을 resize라고 한다. resize를 한칸식 늘린다면 비효율적이므로 일반적으로 2배 큰 크기로 resize 한다. 이를 더블링이라고 한다. resize 덕분에 데이터를 추가 저장할 수 있게 된다.

Dynamic Array 사용법

파이썬은 리스트 자료형을 통해 이미 동적 배열이 잘 구현되어 있다. 중요한건 리스트의 연산법과 시간복잡도만 잘 고려하자

리액트에서 배열과 객체 및 해시 맵을 사용하는 방법

const postsById = {
  1: { id: 1, title: "First Post", content: "Content of first post" },
  2: { id: 2, title: "Second Post", content: "Content of second post" },
};
 
const postIds = [1, 2];
 
function PostList() {
  return (
    <div>
      {postIds.map((id) => (
        <Post key={id} post={postsById[id]} />
      ))}
    </div>
  );
}
 
function Post({ post }) {
  return (
    <div>
      <h2>{post.title}</h2>
      <p>{post.content}</p>
    </div>
  );
}
const posts = {[ { id: 1, title: "First Post", content: "Content of first post" }],[ { id: 2, title: "Second Post", content: "Content of second post" }]}
 
function PostList(){
  return (
    <div>
      {posts.map((post)=>
      <Post key={post.id} post={post}/>)}
    </div>
  )
}
Linked ListQueue