Array(배열), LinkedList(연결리스트)

Array

배열은 보편적으로 동일한 형태의 여러 데이터를 저장하기 위해 사용한다.

한번 고정적으로 선언된 배열은 크기를 변경하기가 어렵다. 

정해진 크기의 데이터를 저장할때 사용하면 좋다.

장점 : 인덱스를 알고 있다면 해당자료를 찾기 쉽다.

단점: 데이터가 삭제되면 해당 인덱스를 비워두어야한다는 단점이 있다.

과일 = ['사과', '수박','바나나','멜론' ,'파인애플' , '포도']
과일[0]

//'사과'

 

ArrayList (배열)

메모리상에 연속된 공간으로 할당됨

파이썬에서는 리스트를 사용한다.

• 리스트는 사이즈 변경이 자유롭고, 타입이 다른요소를 넣을 수 있다.
• 파이썬만 그렇다.
• K번째 원소를 확인/변경이 가능하다.
• 순서가 있고,  중복을 허용한다. 크기가 가변적이다.
• 데이터의 삽입과 삭제에 대한 데이터 낭비가 적다. 

LinkedList (연결리스트)

메모리상에 노드들이 띄엄띄엄 위치하고 이들이 연결되어 있는 구조

파이썬에는 기본 자료형으로 없으므로 필요시 직접구현해야한다.

배열과 반대되는 특성

다른 자료구조를 구현할때 많이 쓰이고, 연결리스트로만 푸는 문제는 없다.

 

ArrayList ↔️ LinkedList 

	ArrayList 내부적으로 배열을 사용	LinkedList 배열사용X
특징	>  인덱스를 통해 데이터 접근 가능	>  하나의 데이터에 다음엘리먼트의 위치정보를 포함
장점	데이터 조회 속도가 빠름 데이터 검색이 빠르다. 단방향 포인터 구조로, 순차적 접근에 유리	데이터 추가, 삭제시 다른데이터에 영향X 삽입삭제 속도가 빠름 양방향 포인터 구조로, 데이터의 삽입, 삭제가 빠름
단점	데이터 추가, 삭제시 다른데이터의 이동이 필요해 시간이 오래걸림 데이터의 삽입, 삭제가 느림	특정데이터를 조회하는 인덱스가 없으므로 ArrayList보다 조회 속도가 느림 데이터의 삽입, 삭제가 빠름

https://docs.python.org/3/tutorial/introduction.html#lists

3. An Informal Introduction to Python — Python 3.10.5 documentation