누워서 떡먹기 코딩

앞에서는 싱글 링크드 리스트를 배웠으니 이제 이중 연결 리스트 (더블 링크드 리스트)를 알아보자. 더블 링크드 리스트는 양방향으로 data, next, prev 3가지 구조로 이루어져 있다. 여기서 prev는 이전 노드를 가르킨다. 다음은 중간 노드 삭제 순서이다.

싱글 링크드 리스트(단순 연결 리스트) 연산들의 시간 복잡도를 알아 보자. 접근 시간 복잡도 인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 가면 된다 마지막 노드에 접근하려면 head에서 다음 노드로 n-1번 가야된다. 최악의 경우 시간 복잡도 : O(n) 탐색 시간 복잡도 배열을 탐색할 때와 같은 방법으로 구한다. 가장 앞 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 갖는 데이터를 찾는다. 이를 선형 탐색이라고 한다. 링크드 리스트안에 찾는 데이터가 없거나 또는 찾으려는 데이터가 마지막 노드에 있는 최악의 경우 n개의 노드를 다 봐야한다. 최악의 경우 시간 복잡도 : O(n) 삽입 / 삭제 시간 복잡도 삽입, 삭제는 그냥 삽입, 삭제할 인덱스의 주변 노드들에 연결된 레퍼런스만..

싱글 링크드 리스트(Linked List) 싱글 링크드 리스트(Linked List) 개념 노드라는 단위의 데이터를 저장하고 데이터가 저장된 각 노드들을 순서대로 연결시켜서 만든 자료구조다. 데이터를 순서대로 저장해준다. 요소를 계속 추가 할 수 있다. 동적배열보다 복잡하다. 연결 리스트라고도 부른다. 노드(Node)에는 data, next라는 2가지 속성이 있다. data에는 저장하고 싶은 정보를 넣는다. next는 다음 노드에 대한 레퍼런스다. 따라서 링크드 리스트는 가장 첫번째의 노드 정보만 알면 next를 타고가서 연결되어 있는 모든 노드를 접근할 수 있다. 첫번째 노드 객체 = head 노드, 마지막 노드 객체 = tail노드 *주의* 링크드 리스트는 실제 메모리에 흩어져있는 형식이다. 예시로 ..

배열 접근 파이썬의 list는 C언어의 배열을 따서 만들었다 차이점이 있다면 C배열은 1. 크기가 고정 2. 같은 타입의 데이터만 담을 수 있다. C언어의 배열은 미리 순서적이고 연속적인 메모리 칸을 쓴다고 예약하고 값을 넣는다 Python의 list는 레퍼런스가 저장되어있고 값을 저장한다기보다는 가리킨다는 의미라서 값이 연속적일 수도 있고 연속적이지 않을 수 도 있다. 배열 탐색 배열 접근 연산 : O(1) 배열 탐색 연산 : O(n) 정적, 동적 배열 정적 배열 : 크기 고정 (요소 수 제한) 동적 배열 : 크기 변함 (요소 계속 추가 가능) 일반적으로 배열은 정적 배열이다. 동적배열은 정적 배열처럼 일정한 메모리를 확보한 후 값을 집어넣는 건데 메모리가 꽉 차면 늘리는 식으로 정적 배열의 크기를 상..

메모리 컴퓨터에는 스토리지와 메모리라는 2가지 데이터 저장 방식이 있다 스토리지 : - 데이터를 영구적으로 저장하는 공간 - 데이터를 저장하는데 오래 걸린다 - 데이터를 받아오는데 오래 걸린다 메모리 : - 데이터를 임시로 저장하는 공간이다 - 데이터를 저장하는데 빠르다 - 데이터를 받아오는데 빠르다 보통 컴퓨터에서 동영상 같은거를 볼때 스토리지에서 메모리로 영상을 복사해서 메모리에서 영상을 재생하고 영상재생이 끝나면 메모리의 데이터가 사라진다. 메모리는 - 일정한 칸이 나눠져있고 - 각 칸에는 데이터를 저장할 수 있다. - 각 칸은 자신만의 주소가 있다. - 메모리 한칸의 기본적인 용량 = 1byte RAM : 임의 접근 메모리 임의 접근 : 저장 위치를 알면 접근할때 항상 일정한 시간이 걸림 메모리에..