1. 선형 배열(Linear Array)

이 글은 "어서와! 자료구조와 알고리즘은 처음이지?" 강의를 듣고 정리한 내용입니다. 😉

 

 

 

선형 배열은 데이터들이 선 (line) 처럼 일렬로 늘어선 형태를 말한다. 보통 프로그래밍에서 배열 (array) 이라고 하면 같은 종류의 데이터가 줄지어 늘어서 있는 것을 뜻하는데, Python 에서는 서로 다른 종류의 데이터 또한 줄세울 수 있는 리스트 (list) 라는 데이터형이 있다.

배열 (array) 이라는 말과 리스트 (list) 라는 말은 개념적인 구조, 즉 데이터를 늘어놓은 모양새를 말할 때는 배열 (array), Python 의 데이터형을 가리킬 때에는 리스트 (list) 라는 용어로 보통 사용한다.

또한, "연결 리스트 (linked list)" 라는 용어와는 구별되어야 한다.

 

Python 리스트에 활용할 수 있는 연산들

리스트 길이과 관계 없이 빠르게 실행 결과를 보게되는 연산들

• 원소 덧붙이기 .append()
• 원소 하나를 꺼내기 .pop()

위 연산들은 리스트의 길이와 무관하게 빠르게 실행할 수 있는 연산들이다. 리스트의 길이가 아무리 길어도 맨 끝에 요소 하나를 추가하는 것이나 맨 끝 요소 하나를 빼는건 빠르게 할 수 있는 일이다. 반면, 리스트가 커지면 그에 따라 실행시간이 길어지는 연산들도 있다.

리스트의 길이에 비례해서 실행 시간이 걸리는 연산들

• 원소 삽입하기 .insert()
• 원소 삭제하기 .del()

이런 연산들은 리스트의 길이가 길면 길수록 처리가 오래 걸리게 된다. 구체적으로 말하면 리스트의 길이예 실행 시간이 비례한다. 리스트 길이가 100 배가 되면, 위 연산들을 실행하는 데 걸리는 시간도 100 배 커진다.

추가 다른 연산

• 원소 탐색하기: .index()