[자료구조] Array & Linked List

leki305·2022년 6월 27일
0

배열(Array)이란?

  • 메모리 상에 데이터를 연속적으로 배치한 자료구조이다.
  • 같은 타입의 데이터를 여러 개 나열한 선형 자료구조이다.
  • 연속적인 메모리 공간에 순차적으로 데이터를 저장한다.
  • 선언할 때 크기를 정하면, 크기가 고정되고 변경할 수 없다.
  • 인덱스를 통해서 요소에 접근할 수 있다.

배열의 시간 복잡도

탐색인 경우

  • 해당 인덱스를 정확하게 알고 있는 접근의 개념일 때 O(1)
  • 무엇이 들어있는지 모르고 찾아야 하는 검색의 개념일 때 O(n)

삽입/삭제인 경우

  • 배열의 끝에 삽입 및 삭제일 때 O(1)
  • 처음 또는 중간일 때 O(n)
    ( 해당 지점의 데이터를 이동시켜야 하기 때문이다. )

장점

  • 항목 접근 속도가 빠르고 일정하다.

단점

  • 크기가 고정되어 있다.
  • 선언 시 크기를 지정해줘야 한다.
  • 배열의 크기가 증가함에 따라 메모리 할당량이 늘어난다.
  • 삽입 / 삭제가 복잡하다.

Python으로 처음 접하고 Python만 배웠는데 Array 라는게 생소하게 들렸기 때문에 차이점이 궁금했다.
List와 Array?

파이썬은 C를 기반으로 만들어졌고 C의 배열을 이용해서 만들어진 언어이지만 다른 구조를 띈다.

  • List가 Array이지만 다른 속성을 띈다.
  • Index도 사용하면서 Pointer처럼 주소 값을 저장하고 요소를 가리키기만 한다.
  • Append, Pop과 같은 배열에서 사용되는 고급 메소드를 지원한다.

파이썬의 배열은 데이터가 연속적일 수도 있고 아예 다른 곳에 저장될 수도 있다.

  • 메모리에 데이터의 주소값을 저장한다.
  • 아무리 큰 값이어도 가리키기만 하는 역활이므로 다양한 값 저장이 가능하다.

그렇다면 파이썬은 리스트인가? 배열인가? 리스트라고 한다. 근본은 배열이지만 결국엔 리스트

그 이유는 배열의 Index는 직접적으로 데이터에 접근이 가능하지만 파이썬의 Index는 몇 번째에 위치하는 데이터인지 알려주는 정도라고 한다.


연결 리스트(Linked List)란?

  • 메모리 상에서 연속적인 공간에 저장되는 특징이 있다.
  • 데이터 및 링크에 의해 비 연속적(비 순차적)으로 연결된 선형 자료구조이다.
  • 고정 크기의 배열 등에 의해 구현된 선형 리스트의 단점을 보완한 자료구조이다.
    • 동적으로 크기가 변할 수 있다.
    • 삭제, 삽입 등에도 데이터 이동의 필요가 없다.
  • 데이터들이 각 노드에 따로 저장되어 있고, 각 데이터마다 다음 순서를 가리키는 Pointer가 존재한다.
    • 다음 순서의 데이터가 뭔지 알려주는 Pointer가 존재한다.
    • 데이터와 포인터를 합쳐 하나의 노드라고 표현한다.

연결 리스트의 특징으로는

  • Pointer로 연결되어 있다.
  • 요소의 접근을 할 때에는 순차적으로 접근한다.
  • 검색면에서는 단점이 될 수 있다.
  • 선형 리스트에 비해 상대적으로 구현이 어렵다.
  • 큐, 스택, 해시 테이블 등의 자료구조의 기반이다.

장점

  • 삽입 / 삭제가 쉽다.

단점

  • 항목 접근이 오래 걸린다. ( 순차적 접근 방식 )
  • 물리적으로 인접한 메모리에 위치해있지 않다.
  • 참조 포인터를 위한 메모리 공간이 낭비된다.

연결 리스트의 종류

단순 연결 리스트

  • 노드들을 한 줄로 연결시킨 기본적인 연결 리스트 자료구조이다.
  • 단방향 ( 각 노드마다 값 및 링크를 갖는다. )

이중 연결 리스트

  • 순방향, 양방향 탐색이 가능하다.
  • 노드마다 2개의 링크를 갖는다.

원형 연결 리스트

  • 마지막 노드의 링크가 리스트의 처음 노드를 가리킨다.
  • 단순 연결 리스트의 처음과 끝을 연결하면 원형 연결 리스트가 된다.

 



Reference

http://www.ktword.co.kr/index.php
https://bluejake.tistory.com/44

0개의 댓글