[자료구조] Array & Linked List

이강일·2022년 6월 27일

배열(Array)이란?

메모리 상에 데이터를 연속적으로 배치한 자료구조이다.

같은 타입의 데이터를 여러 개 나열한 선형 자료구조이다.

연속적인 메모리 공간에 순차적으로 데이터를 저장한다.

선언할 때 크기를 정하면, 크기가 고정되고 변경할 수 없다.

인덱스를 통해서 요소에 접근할 수 있다.

배열의 시간 복잡도

탐색인 경우

해당 인덱스를 정확하게 알고 있는 접근의 개념일 때 O(1)

무엇이 들어있는지 모르고 찾아야 하는 검색의 개념일 때 O(n)

삽입/삭제인 경우

배열의 끝에 삽입 및 삭제일 때 O(1)

처음 또는 중간일 때 O(n)
( 해당 지점의 데이터를 이동시켜야 하기 때문이다. )

장점

항목 접근 속도가 빠르고 일정하다.

단점

크기가 고정되어 있다.
선언 시 크기를 지정해줘야 한다.
배열의 크기가 증가함에 따라 메모리 할당량이 늘어난다.
삽입 / 삭제가 복잡하다.

Python으로 처음 접하고 Python만 배웠는데 Array 라는게 생소하게 들렸기 때문에 차이점이 궁금했다.
List와 Array?

파이썬은 C를 기반으로 만들어졌고 C의 배열을 이용해서 만들어진 언어이지만 다른 구조를 띈다.

List가 Array이지만 다른 속성을 띈다.

Index도 사용하면서 Pointer처럼 주소 값을 저장하고 요소를 가리키기만 한다.

Append, Pop과 같은 배열에서 사용되는 고급 메소드를 지원한다.

파이썬의 배열은 데이터가 연속적일 수도 있고 아예 다른 곳에 저장될 수도 있다.

메모리에 데이터의 주소값을 저장한다.

아무리 큰 값이어도 가리키기만 하는 역활이므로 다양한 값 저장이 가능하다.

그렇다면 파이썬은 리스트인가? 배열인가? 리스트라고 한다. 근본은 배열이지만 결국엔 리스트

그 이유는 배열의 Index는 직접적으로 데이터에 접근이 가능하지만 파이썬의 Index는 몇 번째에 위치하는 데이터인지 알려주는 정도라고 한다.

연결 리스트(Linked List)란?

메모리 상에서 연속적인 공간에 저장되는 특징이 있다.

데이터 및 링크에 의해 비 연속적(비 순차적)으로 연결된 선형 자료구조이다.

고정 크기의 배열 등에 의해 구현된 선형 리스트의 단점을 보완한 자료구조이다.

동적으로 크기가 변할 수 있다.

삭제, 삽입 등에도 데이터 이동의 필요가 없다.

데이터들이 각 노드에 따로 저장되어 있고, 각 데이터마다 다음 순서를 가리키는 Pointer가 존재한다.

다음 순서의 데이터가 뭔지 알려주는 Pointer가 존재한다.

데이터와 포인터를 합쳐 하나의 노드라고 표현한다.