- 메모리 상에 데이터를 연속적으로 배치한 자료구조이다.
- 같은 타입의 데이터를 여러 개 나열한 선형 자료구조이다.
- 연속적인 메모리 공간에 순차적으로 데이터를 저장한다.
- 선언할 때 크기를 정하면, 크기가 고정되고 변경할 수 없다.
- 인덱스를 통해서 요소에 접근할 수 있다.
탐색인 경우
- 해당 인덱스를 정확하게 알고 있는 접근의 개념일 때
O(1)
- 무엇이 들어있는지 모르고 찾아야 하는 검색의 개념일 때
O(n)
삽입/삭제인 경우
- 배열의 끝에 삽입 및 삭제일 때
O(1)
- 처음 또는 중간일 때
O(n)
( 해당 지점의 데이터를 이동시켜야 하기 때문이다. )
Python으로 처음 접하고 Python만 배웠는데 Array 라는게 생소하게 들렸기 때문에 차이점이 궁금했다.
List와 Array?
파이썬은 C를 기반으로 만들어졌고 C의 배열을 이용해서 만들어진 언어이지만 다른 구조를 띈다.
- List가 Array이지만 다른 속성을 띈다.
- Index도 사용하면서 Pointer처럼 주소 값을 저장하고 요소를 가리키기만 한다.
- Append, Pop과 같은 배열에서 사용되는 고급 메소드를 지원한다.
파이썬의 배열은 데이터가 연속적일 수도 있고 아예 다른 곳에 저장될 수도 있다.
- 메모리에 데이터의 주소값을 저장한다.
- 아무리 큰 값이어도 가리키기만 하는 역활이므로 다양한 값 저장이 가능하다.
그렇다면 파이썬은 리스트인가? 배열인가? 리스트라고 한다. 근본은 배열이지만 결국엔 리스트
그 이유는 배열의 Index는 직접적으로 데이터에 접근이 가능하지만 파이썬의 Index는 몇 번째에 위치하는 데이터인지 알려주는 정도라고 한다.
- 메모리 상에서 연속적인 공간에 저장되는 특징이 있다.
- 데이터 및 링크에 의해 비 연속적(비 순차적)으로 연결된 선형 자료구조이다.
- 고정 크기의 배열 등에 의해 구현된 선형 리스트의 단점을 보완한 자료구조이다.
- 동적으로 크기가 변할 수 있다.
- 삭제, 삽입 등에도 데이터 이동의 필요가 없다.
- 데이터들이 각 노드에 따로 저장되어 있고, 각 데이터마다 다음 순서를 가리키는 Pointer가 존재한다.
- 다음 순서의 데이터가 뭔지 알려주는 Pointer가 존재한다.
- 데이터와 포인터를 합쳐 하나의 노드라고 표현한다.
- Pointer로 연결되어 있다.
- 요소의 접근을 할 때에는 순차적으로 접근한다.
- 검색면에서는 단점이 될 수 있다.
- 선형 리스트에 비해 상대적으로 구현이 어렵다.
- 큐, 스택, 해시 테이블 등의 자료구조의 기반이다.
단순 연결 리스트
- 노드들을 한 줄로 연결시킨 기본적인 연결 리스트 자료구조이다.
- 단방향 ( 각 노드마다 값 및 링크를 갖는다. )
이중 연결 리스트
- 순방향, 양방향 탐색이 가능하다.
- 노드마다 2개의 링크를 갖는다.
원형 연결 리스트
- 마지막 노드의 링크가 리스트의 처음 노드를 가리킨다.
- 단순 연결 리스트의 처음과 끝을 연결하면 원형 연결 리스트가 된다.
http://www.ktword.co.kr/index.php
https://bluejake.tistory.com/44