[자료구조] 파이썬(Python) VS 자바(Java) 주요 자료구조 비교해보기

파이썬과 자바의 주요 자료구조를 비교해보았다.

 

비교항목 

• Array : Java Array VS Python List
• List : Java ArrayList VS Python List
• LinkedList : Java LinkedList VS Python Collections.deque 
• Map : Java HashMap VS Python Dictionary 
• Set : Java HashSet VS Python Set

1. Array : Java Array VS Python List 

Java Array 

자바에서 배열(Array)의 크기는 정적(static)이기 때문에 각 요소의 값을 변경하는 것은 가능하지만 크기를 줄이거나 늘릴 수 없다. 처음 선언된 배열의 크기를 변경하는 경우 새로운 메모리 블록이 힙 영역에 할당되고 새로운 메모리 주소가 생긴다. 아래의 코드예시는 자바의 Array의 초기화 방법이며 초기화시 지정된 길이만큼 아이템을 넣을 수 있다. 만약 배열의 크기를 변경한다면 numArr과 numArr2의 메모리주소가 새롭게 만들어지게 된다. 

//고정된 크기로 초기화 
int[] numArr = new int[5]; // 배열의 크기는 5개로 고정 
IntStream.range(0,5).forEach(i -> numArr[i]=i+1); //1부터 5까지 할당

//고정된 값으로 초기화 , 요소의 개수만큼 배열의 크기가 고정
int[] numArr2 = {1,2,3,4,5};

 

Python List 

파이썬에서는 array 모듈이 있지만 여러 단점(이 글에서는 설명은 생략) 때문에 잘 쓰지 않고 List가 배열(Array)의 일을 대신한다.

그림예시처럼 파이썬에서 List의 요소에 담기는 것은 객체 자체가 아니라 객체를 가리키는 참조(reference)/포인터를 가지고 있다. 따라서 타입이 여러개가 허용되며, 동적으로 List의 크기를 변경하여도 메모리주소는 그대로이다. 

my_List = [1,"hi",10.1] // 여러타입의 요소가 허용됨 
my_List.append("spongeBob"); //요소 추가
my_List.pop(); //마지막 요소 삭제

2. List : Java ArrayList VS Python List

Java ArrayList 

자바의 ArrayList는 동적배열(Dynamic Array)를 구현한 클래스로서 인스턴스 선언 후에 리스트의 크기를 늘리거나 줄일 수 있다.    Collection 프레임워크에 속해있으며 List 인터페이스를 구현한다.  ArrayList는 제네릭이 있기에 같은 타입만 할당될 수 있다는것을 제외하면 Python의 List와 매우 유사하다. 

// ArrayList 인스턴스 선언 (처음에는 리스트의 크기가 0이다)
List<String> arrStr = new ArrayList<String>();
// 리스트에 동적으로 아이템을 추가하여 크기를 늘림
arrStr.add("Danny");
arrStr.add("Michael");

//Michael 삭제해서 리스트의 크기 줄임 
arrStr.remove(1);

3.LinkedList : Java LinkedList VS Python collections.deque

자바와 파이썬의 LinkedList 구조를 이해하기 위해서는 단일 연결리스트(Singly LinkedList)와 이중연결리스트(Doubly LinkedLIst)의 접근법을 알아야한다. 아래의 그림의 #LinkedList가 단일연결리스트(Singly LinkedList)를 나타내며 그 밑에 이중연결리스트(Doubly LinkedList)를 설명해두었다. 

쉽게 정리하자면 단일 연결리스트(Singly LinkedList)는 항상 첫번째 노드를 통해 접근되고, 이중연결리스트(Doubly LinkedList)는 첫번째 노드와 마지막 노드를 통해 접근할 수 있다. 

 

Java LinkedList 

자바의 LinkedList는 이중연결리스트(Doubly LinkedList)로 구현되어있다. 따라서 첫번째 노드와 마지막 노드로의 접근은 상수시간(O(1)) 이 소요되며, 중간에 있는 노드에 접근 시에는 선형시간(O(n))이 소요된다.

LinkedList<String> listStr = new LinkedList<String>();
listStr.add("apple");
listStr.add("orange");
listStr.add("grape");

//처음과 끝에 요소 추가 , 상수시간 소요
listStr.addFirst("banana"); 
listStr.addLast("cherry");

 

Python collections.deque

파이썬에서는 collections 모듈의 deque를 이용해 자바의 LinkedList와 매우 동일하게 사용할 수 있다. deque의 자료구조도 양끝의 노드의 포인터값이 힙 메모리 영역에 저장되있기 때문에 맨앞과 맨끝의 노드 접근 시 상수시간(O(1))이 걸린다. 

Linked_List = collections.deque({}) 
Linked_List.append(10)
Linked_List.append(False)

Linked_List.appendleft("new item") //맨앞에 아이템 추가 
Linked_List.popleft() //맨앞 아이템 삭제 
Linked_List.pop() //가장 끝 아이템 삭제

4.Map : Java HashMap VS Python Dictionary 

HashMap과 HashSet에 들어가기 앞서, Hash함수가 자료구조에서 어떻게 사용되는지 알아야한다.

그림 예시는 HashTable의 예시이다. HashTable 은 배열(Array) 자료구조를 기반으로 두고 있기 때문에 내부적으로 인덱스가 존재하며 인덱스마다 엔티티를 저장하는 장소인 버킷(bucket)으로 구성되어있다.  HashTable의 엔티티는 key와 value로 구성되어있으며, HashTable에 저장되기 전에 Hash함수를 사용하여 Key값을 인덱스로 변환 후 해당 인덱스 위치에 있는 버킷에 값을 저장한다.

key 값을 아스키코드로 변환 후 내부 메커니즘에 의해 인덱스로 변환해주고, 해당 인덱스의 버킷 자리에 엔티티가 들어가게 된다.

 

중요한 점은 Hash함수는 일방향 함수(one-way function)이기 때문에 내부에 인덱스가 구성되어있어도 인덱스를 가지고 키를 찾는 것은 불가하다. 일방향 함수(one-way function)란 특정 입력에 대해 고유한 출력을 생성하지만, 출력으로부터 입력을 역으로 찾는 것은 어려운 함수를 말한다. 

 

Java HashMap

HashMap도 내부적으로 배열(array)의 형태를 가지고 있으며, 각각의 엔티티는 key-value로 구성되어있다.  Hash함수를 이용하여 엔티티의 key값을 이용해 인덱스를 생성하고 특정 버킷에 엔티티를 저장시킨다.  key값만 안다면 상수시간O(1)에 아이템을 찾아낼 수 있는 자료구조이다. 

HashMap<String,Integer> products = new HashMap<>();
products.put("새우깡",1000);
products.put("포카칩",1200);
int shrimpPrice = products.get("새우깡");  //key값으로 값을 찾음 
System.out.println(shrimpPrice); // 1000

 

Python Dictionary 

파이썬의 Dictionary는 HashTable을 기반으로 두고 있으며 자바의 HashMap과 동일하게 Hash함수를 사용한다. 아이템은 key-value로 구성되어있으며 , key값은 해시값으로 변환되어 인덱스를 생성하고 특정 버킷에 아이템를 저장시킨다.  key값만 안다면 상수시간O(1)에 아이템을 찾아낼 수 있는 자료구조이다. 

food_price={
    'Pizza' : 10000,
    'Bretzel' : 5000,
    'Bibimbap' : 5000
}

pizza_price = food_price['Pizza'] //key값으로 값을 찾음 
print(pizza_price) // 10000

 

 

(!!!)

자바에서는 key-value 쌍을 엔티티(entity)라고 부르고 파이썬은 아이템(item)이라는 용어를 사용하는 이유

-> 찾아본 결과 둘이 같은 의미이며 언어의 관례에 따라 부르는 용어가 다른 것이라고 한다.  자바에서는 엔티티(entity)라는 용어를 많이 사용하는데, 이는 자바가 객체지향 프로그래밍에서 객체를 엔티티라고 부르는 것이 관례이기 때문이다. 반대로 파이썬의 딕셔너리 메소드 중에 items()는 모든 아이템을 반환한다. 이것도 파이썬에서 key-value 쌍을 아이템이라고 부르는 관례에 영향이 간것이라고 한다. 

5. Set : Java HashSet VS Python Set 

Java HashSet

자바의 HashSet은 Set 인터페이스를 구현한 클래스 중 하나로 HashMap을 기반으로 중복을 허용하지 않는 원소들의 집합을 관리한다. HashMap과 다른 점은 key-value의 쌍이 저장되는 것이 아니라 유일한 key만을 저장하고 이것이 곳 value가 된다. 

내부적으로 Hash함수가 구현되어 특정 인덱스의 버킷에 저장되지만, key가 곧 value가 되기 때문에 key값을 이용하여 검색하는 get()메소드의 사용이 불가하며 값의 여부를 알고싶다면 contains()메소드를 사용한다. 

HashSet<String> fruits = new HashSet<>();
fruits.add("apple");
fruits.add("banana");

String targetKeyValue = "apple";

if(fruits.contains(targetKeyValue)){
	System.out.println(targetKeyValue + "는 HashSet에 포함되있음");
}else{
    System.out.println(targetKeyValue + "는 HashSet에 포함안되어있음");
}

 

 

Python Set

파이썬의 set은 내부적으로 HashTable을 기반으로 구성되어있다. 자바의 HashSet과 유사하게 key자체가 곧 value가 되며 고유한 해시값을 갖게 된다. 중복을 허용하지 않으며 value자체가 key로 활용되기 때문에 key로 값을 찾는 것은 불가하며 in연산자를 사용하거나 set객체의 __contains__메소드를 사용한다.

fruits = {'apple','banana'}

if 'banana' in fruits:
	print('set에 banana가 있음')
    
if fruits.__contains__('banana'):
	print('set에 banana가 있음')

 

 

---

출처

https://ko.wikipedia.org/wiki/%EC%9D%BC%EB%B0%A9%ED%96%A5%ED%95%A8%EC%88%98

일방향함수 - 위키백과, 우리 모두의 백과사전

https://paciencia.tistory.com/118?category=859828

[Java/Python] 문법 비교 정리 #7 자료구조 - HashMap(Dictionary)