자료구조, 리스트(List) 와 배열(Array)

Array 란 무엇인가?

배열이란 간단히 이야기하면 여러개의 데이터의 묶음이라고 할 수 있다. 많은 개발자들이 배열하면 굉장히 익숙하게 와닿을 수 있는 것은 어느 언어에나 있는 배열이라는 자료구조가 존재하기 때문이다. 그래서 한번이라도 사용해본 경험이 있다면 인덱스 번호로 원하는 배열에 접근하는 것을 볼 수 있을 것이다.

1
2
3
4

const arr = ['Apple', 'Banana', 'Pineapple'];
console.log(arr[0]); // Apple
console.log(arr[1]); // Banana
console.log(arr[2]); // Pineapple

그래서 배열은 한 문장으로 표현한다고 한다면 고유한 식별자(Index 번호) 와 그 식별자에 대응하는 데이터의 묶음 으로 표현할 수 있다. 다른 한편으로는 고유한 식별자를 첨자 라고도 부른다.

Array 의 특성

위에서 Javascript 코드로 봤듯 배열은 접근에 굉장히 용이하다. 데이터들이 연속된 메모리 영역에 순서대로 저장되기 때문이다. 그러한 연속된 저장으로 인해 인덱스 번호를 이용해서 빠르게 접근을 할 수 있다. 이 것은 임의 접근(Random access) 이라고 표현한다.

반대로 추가나 삭제를 해야하는 경우는 배열에서는 용이하지 않다. 위에서 설명한 예제를 가지고 데이터의 추가를 그림으로 표현한다면 아래와 같이 나온다.

만약 새로운 배열 Melon 을 Apple와 Banana 사이에 추가를 하려고 하는 경우 현재는 배열의 공간이 없다. 그래서 공간을 추가를 위해 맨 마지막에 새로운 공간을 추가했다.

그 후, Pineapple 부터해서 Banana 까지 차례로 오른쪽으로 하나씩 이동시킨다.

그렇게 공간이 남으면 해당 공간에다가 원하는 Melon을 추가할 수 있게 된다.

삭제 역시 위와 같이 쉽지 않다. 만약 위에서 추가한 Melon 을 다시 삭제하려고 한다면 아래와 같이 일단 먼저 Melon을 지운다.

배열은 연속된 메모리 영역에 순서대로 저장된다는 특성 때문에 위처럼 지우고 나면 해당 공간으로 다시 데이터들을 밀어줘야 한다.

위처럼 다 지워주고 나면 남은 공간을 제거 해주면 된다.

List 란 무엇인가?

위키 백과에서는 같은 값이 한 번 이상 존재할 수 있는 일련의 값이 모여있는 추상적 자료형이라고 정의 하고 있다. 나와 같은 Javascript 로 개발을 처음 접한 개발자에게는 List 와 Array 에 대한 차이를 단번에 이해하기 힘들 수도 있다.(물론 필자만 그럴 수도 있고..) list 역시 array 와 마찬가지로 데이터가 일직선으로 나열되어 있는 형태로 되어 있다. 그럼 array 와의 차이점이 무엇일까? 리스트는 array 와는 다르게 연속된 위치가 아닌 떨어진 영역에 저장된다는 점이다.

List 의 자료 구조는 위와 같이 생겼다. list 의 경우 pointer 라는 개념이 있는 데 이 pointer 란 다음 메모리의 위치를 가르키고 있다. List 를 대략적으로 알기 위해서는 보물 찾기를 생각하면 좋을 것 같다. 1번 목적지에서 다음 2번 목적지에 대한 하는 힌트 혹은 지도를 얻은 후, 2번에서는 다음 목적지를 찾는 것과 같다. 보물찾기를 해본 사람은 알겠지만 목적지에 다다르기 위해서는 차례로 1번 목적지부터 2번,3번.. n번 까지 다 거쳐서 목적지에 들려야함을 알 수 있다. 물론 당연히 1번 목적지를 거치지 않고 처음부터 2번으로 도전할 수 없듯이 말이다.

List 의 특성

위에서 보물찾기와 같이 설명했듯 리스트 의 경우 배열과 다르게 임의 접근(Random access) 을 할 수 없다. 리시트 의 경우에는 순차 접근 혹은 시퀀셜 엑세스(Sequential access)를 이용해야 한다. 위의 리스트의 자료 구조에 대한 이미지를 보면 알 수 있 듯 만약 사용자가 Pineapple 에 접근하려 한다면 Apple 을 거쳐 Banana 를 거쳐서 접근을 해야 한다. 다만 리스트의 장점은 배열과는 다르게 공간이 한정되어 있는 것이 아니라 동적 자료 구조 여서 시시각각 데이터의 크기가 변할 수 있으며, 추가와 삭제가 배열과 다르게 훨씬 편하게 가능하다. 배열의 경우는 위에서 봤듯 요소를 추가할 때마다 공간을 확보해서 나머지 요소를 미루는 등의 성능을 저해하는 작업들이 많지만, 리스트의 경우 포인터 만 변경해주면 된다.

만약 위에 처럼 Melon 이라는 요소를 추가해주려고 한다면 어떻게 하면 될까?

그런 경우라면 Apple의 포인터만 바꿔주면 될 것이다. 위에서 말했듯 리스트의 포인터는 다음 메모리의 위치를 가르키고 있다.

마찬가지로 삭제 역시 포인터만 변경해주면 된다. 만약 Banana 에 대한 요소를 제거하려고 하면 포인터만 Melon 의 포인터만 변경해주면 된다.

Banana 의 포인터는 따로 제거할 필요가 없다. 왜냐하면 어차피 해당 데이터에 접근을 할 때는 Apple 이라는 Head 에서부터 접근을 해야하기 때문에 Banana 로 접근할 수 없기 때문이다. 또한 이 영역 역시 이후에 재사용할 때는 덮어쓰기가 되기 때문에 별도로 삭제해줄 필요 역시 없다.

Array 와 List 의 각각 시간 계산

위에서처럼 Array 와 List 에는 각각의 차이점이 있다. 물론 필자와 같이 Javascript 로만 개발을 하는 경우에는 그 어떤 데이터를 선택해야 하는지에 대한 고민을 안해도 되지만 그 외의 서버 개발자에게는 아마 필요에 따라 데이터를 잘 선택하는 것이 중요하다. 아래는 Array 와 List 의 시간 계산에 대한 표이다. 아래의 표를 참고해서 상황과 목적에 맞는 데이터를 선택해서 사용하길 바란다.

출처

위키백과)