CS (6) 썸네일형 리스트형 [자료구조] 단순 연결 리스트( Singly Linked List ) 한쪽으로만 연결이 되어 있는 자료구조입니다. 단순 연결 리스트 의 가장 큰 특징은 연속되지 않은 데이터끼리의 연결 입니다. 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다. 원하는 위치의 데이터의 추가는 O(n+1) 의 시간복잡도를 갖습니다. 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다. 원하는 위치의 데이터의 제거는 O(n+1) 의 시간복잡도를 갖습니다. 데이터에 순차적으로 접근해야 해서 데이터 접근 속도가 느립니다. ex) list.head.next?.next?.next?.value 다음 데이터의 연결을 저장하는 공간이 필요해서 공간 효율이 좋지 않습니다. Singly Linked List 를 이해하기 쉽게 그림으로 나타내면 아래와 같습니다. 아래 그림과 같이 동작하게 됩니다. fisrt Si.. [자료구조] 순차 리스트 ( Sequential List ) 미리 알림 내용 읽다 보시면 이거 배열이랑 다를게 뭐야.. 라고 생각하실텐데, 배열이란 길이가 한정적인 연속된 자료구조 입니다. 하지면 저희가 쓰는 Swift 의 Array 는 길이가 유동적입니다. 그래서 Array 는 순차 리스트의 일종이구나~ 하고 봐주시면 됩니다. 데이터를 연속해서 저장하는 자료구조입니다. 순차 리스트의 가장 큰 특징은 데이터를 메모리 상에 연속된 위치에 저장한다. 입니다. 데이터의 추가, 제거에 오버헤드가 발생하지만, 인덱스를 사용해 데이터에 빠르게 접근이 가능합니다. 데이터는 어디에서나 추가가 가능하므로, append 의 경우 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다. insert 의 경우 데이터의 추가는 O(N) 의 시간복잡도를 갖습니다. 데이터는 어디에서나 제거가 가.. [자료구조] 덱 ( Deque ) Double Ended Queue 를 줄여서 덱 ( Deque ) 이라고 부릅니다. 양 쪽에 뚜껑이 달린 프링글스같은 자료구조입니다. 덱의 가장 큰 특징은 양방향 데이터 추가, 제거가 가능한 큐 ( Queue ) 이며, 큐와 스택에 비해 자유도가 높습니다. 데이터는 처음 또는 마지막에 추가되므로, 스택, 큐와 동일하게 뒤에서 데이터를 추가할 경우 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다. 앞쪽에서 데이터를 추가할 경우, 오버헤드를 방지하지 않는다면 데이터의 추가는 O(n) 의 시간복잡도를 갖습니다. 앞쪽에서 데이터를 추가할 경우, 오버헤드를 방지한다면 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다. 데이터는 처음 또는 마지막에 제거되므로, 스택과 동일하게 앞에서 데이터를 제거할 경우 데이터의.. [자료구조] 자료구조 로드맵 자료구조란, 데이터를 상황에 맞게 저장하기 위한 구조입니다. * 아래 목록 중 링크가 활성화 되어 있는 것은 블로그에 정리 되어 있는 부분입니다. 단순 구조 정수 실수 문자 문자열 선형 구조 순차 리스트 연결 리스트 단순 연결 리스트 이중 연결 리스트 원형 연결 리스트 스택 큐 덱 비선형 구조 트리 일반 트리 이진 트리 그래프 방향 그래프 무방향 그래프 파일 구조 순차 파일 색인 파일 직접 파일 [자료구조] 큐 ( Queue ) 개요 맛집 대기줄 같은 자료구조 입니다. 큐의 가장 큰 특징은 선입선출( FIFO, First-In-First-Out ) 이며, 먼저 들어온 데이터가 먼저 나간다는 의미입니다. 구현하는 방식에 따라 오버헤드가 발생할 수도 있고, 발행하지 않을 수도 있습니다. 데이터는 마지막에 추가되므로, 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다. 먼저 들어온 데이터가 제거되므로, Head 자체를 삭제하는 경우 배열을 하나씩 당겨줘야 하기 때문에 데이터의 제거는 O(n) 의 시간복잡도를, Head 를 가리키는 인덱스를 변경시킬 경우 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다. Queue 를 이해하기 쉽게 그림으로 나타내면 아래와 같습니다. head Queue 에서 제일 먼저 제거할 테이터입니다. enque.. [자료구조] 스택 ( Stack ) 개요 하나하나 쌓아올리는 자료구조 입니다. 스택의 가장 큰 특징은 후입선출( LIFO, Last-In-First-Out ) 이며, 마지막으로 들어온 데이터가 먼저 나간다는 의미입니다. 배열을 움직일 필요가 없어서 오버헤드가 발생하지 않습니다. 데이터는 마지막에 추가되므로, 데이터의 추가는 O(1) 의 시간복잡도를 갖습니다. 데이터는 마지막에서 제거되므로, 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다. Stack 을 이해하기 쉽게 그림으로 나타내면 아래와 같습니다. 아래 그림과 같이 동작하게 됩니다. Top Stack 의 상단 데이터입니다. 제일 마지막에 들어온 데이터입니다. Push Stack 에 데이터를 추가합니다. 마지막으로 Push 한 데이터가 Top 입니다. Pop Stack 에서 데이터를 .. 이전 1 다음
