자료구조, 리스트에 대해(Feat. 배열과 리스트의 차이점)

* 자료구조의 가장 간단한 부분인 리스트이다.

 

저번 학기에 도전했던 몇몇 회사 필테에 링크드리스트 구현 코드가 나왔었다.

 

기초가 부족했던 나는 폭망했다 ㅎ... 그래서 종강하면 바로 링크드리스트부터 공부해야겠구나 마음을 먹었다.

 

강하고 보름 내내 놀다가 이틀정도 공부했다. ㅎ 그래서 조금 허접하다.

 

암튼, 각색하고

 

리스트를 알기 전에 우선 가장 기본적인 배열을 알아보도록 하자.

 

배열의 가장 큰 특징은 인덱스를 가지고 있고, 초기에 배열의 크기가 정해진다.

 

그러고 인덱스 0부터 주어진 배열의 크기 -1 까지 데이터가 해당 인덱스에 따라 데이터를 여러개 가질 수 있는 자료구조이다.

 

그렇다면 리스트는 무엇인가?

 

리스트에는 크게 두 가지 종류가 있다. 바로 순차리스트와 연결 리스트다.

 

1.     순차 리스트 : 배열을 기반으로 구현된 리스트(ex. ArrayList)

     A.     장점> 배열과 마찬가지로 인덱스를 사용하기 때문에 데이터를 찾는데 빠르다

     B.      단점> 중간 데이터 삽입과 삭제가 느리다.

 

2.     연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트(ex. LinkedList)

     A.     장점> 데이터를 삭제하고 삽입하는데 빠르다.

     B.      장점> List의 크기를 정하지 않아도 된다.

     C.      단점> 데이터를 찾는 게 느리다.

     D.     특징> 연결 리스트는 한 노드에 연결될 노드의 포인터 위치를 가리킨다.

            데이터를 중간에 넣고 뺀다고 해도 이전에 가리키는 값, 다음 값이 가리켰던 값만 연결해주면 되기 때문에

            중간 삽입, 삭제가 빠르다.

 

ArrayList는 내가 JAVA에서 가장 많이 쓰는 자료구조이다.

 

LinkedList는 JAVA에서 보통 Queue를 구현할 때 이를 이용해서 만든다.

 

리스트의 큰 특징 두가지를 잡아보자면

 

1.     리스트는 데이터를 나란히 저장한다.

2.     데이터의 중복된 저장을 막지 않는다. 즉, 수학적 ‘집합’과 개념이 다르다.

 

이렇게 된다.

 

배열과의 차이점? 장단점을 비교하자면

 

	장점	단점
배열	인덱스가 있어 검색이 빠름	중간 삽입, 삭제가 어려움
연결 리스트	중간 삽입, 삭제가 빠름	검색이 느림.

 

이렇게 된다.

 

정리하자면, 

 

List : 순서가 중요하며(검색을 위하여, 연결 리스트는 검색하기 위해 순차 탐색을 실시한다.), 중간 위치에 값을 추가, 삭제 되는 경우 List를 사용하는 것이 좋다.

 

Array: 반대로 순서는 상관없지만 순차적으로만 추가, 삭제되는 데이터는 Array를 사용하는 것이 좋다.

 

이렇게 된다.