~프로로그~
리스트에 대해서 알아보자~!
현재 필자는 리스트의 개념이 확실하다고 생각하나 어째 코딩이 안된다.
미칠듯하다. 리눅스환경에서 코딩하다가 visual c++이용하려니깐 복잡해서 안된다.
vmware로 리눅스롤 설치하던지.... 므튼... 리스트 코드는 다음에 하기로하고 일단!!
리스트의 개념에 대해서 알아보자!
----------------------------------------------------------------------------
1. 리스트
자료를 순서대로 저장하는 자료구조를 말한다. 선형구조를 이룬다!
- 리스트의 기능(추상자료형으로 나타내고 싶었으나... 귀차니즘이...;;)
ⓐ 리스트 생성 - 최대 Max를 가지는 공백 리스트를 구성해준다.
ⓑ 리스트 삭제 - 리스트를 삭제한다.
ⓒ 자료 추가 가능 여부 - 현재 자료 개수와 최대 자료개수를 비교해여 추가 가능성을 나타낸다.
ⓓ 자료 추가 - 원하는 위치와 값을 받아 자료를 추가해준다.
ⓔ 자료 제거 - 제거하는 위치를 받아 그 자료를 제거해준다.
ⓕ 자료 검색 - 원하는 위치의 자료를 반환해준다.
(상황에 따라 일정 자료를 주고, 그 자료의 위치를 반환하는 것으로 만들수 있다.)
ⓖ 리스트 보기 - 리스트의 모든 자료를 보여준다.
- 배열 리스트 vs 연결리스트
ⓐ add(), delete()
ㄱ. 배열 : 원소의 추가와 제거시 밀어내기 현상이 일어난다.
위에서는 한개를 밀어내는 것을 보았지만, 자료가 많으면 많을수록 이러한 현상(밀어내기)이 심하게 일어난다.
※ 자료를 추가 제거시 밀어내기 방향에 주의해자!! >> 방향이 틀리면 자료값이 달라질수 있다!
ㄴ. 연결리스트 : 자료와 링크로 구성된 노드들의 집합.
자료 제거시 메모리를 꼭 해제 해줘야 한다. 그렇지 않으면 많은 메모리 누수로 크리티컬 한방!!
ⓑ 자료검색(특정 Index값 도출)
배열의 경우 해당 Index를 통해 한번에 찾아가 자료를 산출할수 있다.(빅오 : O(1))
연결리스트의 경우는 처음부터 Index 지점 까지 이동후 산출이 가능하다.(빅오 : O(n))
>>즉, 배열이 자료 검색에 유용하다!!
ⓒ 그 외 기능
리스트에서 주로 쓰는 기능이자 차이가 나는 것은 추가, 삭제, 검색 이 3가지 기능이다.
그 외 기능들은 외부적인 것으로 두개 모두 비슷한 방식으로 계산된다.
따라서 배열이냐 리스트냐를 구분하여 생각할 필요가 없다고 생각된다.
ⓓ 배열 리스트 vs 연결 리스트 결말!!
- 연결 리스트가 우수한 점!!
> 추가 자료 이동(밀어내기현상)이 없다.
> 최대 원소 개수 정의할 필요가 없다. 불필요!!
>>> 자료의 탐색 보다는 추가 삭제가 중심인 알고리즘에 적용.
- 배열 리스트가 우수한 점!!
> 단순하다!
> 탐색 연산의 비용이 높다!
>>> 자료의 추가가 삭제가 적고 탐색이 중점인 알고리즘에 적용.
-----------------------------------------------------------------------------------------
~에피로그~
리스트의 기본적인 면과 각각 연결 리스트와 배열 리스트가 돌아가는 것을 보았다.
이에대한 소스는 밤에 작성하여 올리도록 꼭 노력하겠다!
다음시간에는 연결 리스트의 종류인 단순 연결리스트, 원형 연결리스트, 이중 연결리스트를 알아보겠다~
리스트에 대해서 알아보자~!
현재 필자는 리스트의 개념이 확실하다고 생각하나 어째 코딩이 안된다.
미칠듯하다. 리눅스환경에서 코딩하다가 visual c++이용하려니깐 복잡해서 안된다.
vmware로 리눅스롤 설치하던지.... 므튼... 리스트 코드는 다음에 하기로하고 일단!!
리스트의 개념에 대해서 알아보자!
----------------------------------------------------------------------------
1. 리스트
자료를 순서대로 저장하는 자료구조를 말한다. 선형구조를 이룬다!
- 리스트의 기능(추상자료형으로 나타내고 싶었으나... 귀차니즘이...;;)
ⓐ 리스트 생성 - 최대 Max를 가지는 공백 리스트를 구성해준다.
ⓑ 리스트 삭제 - 리스트를 삭제한다.
ⓒ 자료 추가 가능 여부 - 현재 자료 개수와 최대 자료개수를 비교해여 추가 가능성을 나타낸다.
ⓓ 자료 추가 - 원하는 위치와 값을 받아 자료를 추가해준다.
ⓔ 자료 제거 - 제거하는 위치를 받아 그 자료를 제거해준다.
ⓕ 자료 검색 - 원하는 위치의 자료를 반환해준다.
(상황에 따라 일정 자료를 주고, 그 자료의 위치를 반환하는 것으로 만들수 있다.)
ⓖ 리스트 보기 - 리스트의 모든 자료를 보여준다.
- 배열 리스트 vs 연결리스트
ⓐ add(), delete()
ㄱ. 배열 : 원소의 추가와 제거시 밀어내기 현상이 일어난다.
위에서는 한개를 밀어내는 것을 보았지만, 자료가 많으면 많을수록 이러한 현상(밀어내기)이 심하게 일어난다.
※ 자료를 추가 제거시 밀어내기 방향에 주의해자!! >> 방향이 틀리면 자료값이 달라질수 있다!
ㄴ. 연결리스트 : 자료와 링크로 구성된 노드들의 집합.
자료 제거시 메모리를 꼭 해제 해줘야 한다. 그렇지 않으면 많은 메모리 누수로 크리티컬 한방!!
ⓑ 자료검색(특정 Index값 도출)
배열의 경우 해당 Index를 통해 한번에 찾아가 자료를 산출할수 있다.(빅오 : O(1))
연결리스트의 경우는 처음부터 Index 지점 까지 이동후 산출이 가능하다.(빅오 : O(n))
>>즉, 배열이 자료 검색에 유용하다!!
ⓒ 그 외 기능
리스트에서 주로 쓰는 기능이자 차이가 나는 것은 추가, 삭제, 검색 이 3가지 기능이다.
그 외 기능들은 외부적인 것으로 두개 모두 비슷한 방식으로 계산된다.
따라서 배열이냐 리스트냐를 구분하여 생각할 필요가 없다고 생각된다.
ⓓ 배열 리스트 vs 연결 리스트 결말!!
- 연결 리스트가 우수한 점!!
> 추가 자료 이동(밀어내기현상)이 없다.
> 최대 원소 개수 정의할 필요가 없다. 불필요!!
>>> 자료의 탐색 보다는 추가 삭제가 중심인 알고리즘에 적용.
- 배열 리스트가 우수한 점!!
> 단순하다!
> 탐색 연산의 비용이 높다!
>>> 자료의 추가가 삭제가 적고 탐색이 중점인 알고리즘에 적용.
-----------------------------------------------------------------------------------------
~에피로그~
리스트의 기본적인 면과 각각 연결 리스트와 배열 리스트가 돌아가는 것을 보았다.
이에대한 소스는 밤에 작성하여 올리도록 꼭 노력하겠다!
다음시간에는 연결 리스트의 종류인 단순 연결리스트, 원형 연결리스트, 이중 연결리스트를 알아보겠다~