STUDY/자료구조3 [Python] Linked List 개념링크드 리스트노드(구조체)가 연결되는 형식으로 데이터를 저장하는 자료구조배열과의 차이점 : 배열은 논리적으로도 물리적으로도 연속적인 반면, 링크드리스트는 논리적으로 연속적이지만 물리적으로는 비연속적이다. Singly Linked List- 각 노드가 (value를 담고있는 'data' + 다음 노드를 가리키는 주소 'next')로 구성된다.- head(맨 앞)에서부터 읽기 시작하여 tail(맨 뒤)까지 읽을 수 있지만 역순으로는 읽을 수 없다.- 접근 및 탐색은 O(n), 삽입 및 삭제는 O(1)의 시간복잡도를 가진다. Doubly Linked List- 이전 노드로 갈 수 있는, 즉, 양방향의 노드 이동이 가능한 형태의 링크드리스트이다.- 각 노드가 (이전 노드를 가리키는 주소 'prev' + va.. 2025. 4. 9. [Python] List 개념리스트순서를 가지고 데이터를 저장하는 선형 자료구조.빈 공간을 허용하지 않는 자료구조이므로, 원소 제거 시 뒤쪽의 원소들이 앞당겨지고 삽입 시에는 뒤쪽의 원소들이 뒤로 밀리게 된다.따라서, 원소 삽입/삭제 시 재정렬로 인한 O(n)의 시간복잡도 증가에 주의하여야 한다. 리스트 선언a = list() - a라는 리스트를 선언. a = [1, 2, 3] - a라는 리스트를 선언하고 각 원소를 1,2,3으로 정의. a = [[1, 1, 1], [2, 2, 2], [3, 3, 3]] - 2차원 리스트 (좀 더 직관적으로 나타내기 위해서는 아래처럼 작성)a = [[1,1,1],[2,2,2],[3,3,3]] 원소 업데이트a[0] = 3 - 0번째 인덱스의 원소를 3으로 수정한다.a[0][1] = 3 .. 2025. 4. 8. [Python] Stack과 Queue 개념 구분Stack (Last-in, First-out)Queue (First-in, First-out)리스트의 종류Array ListLinked List활용페이지 뒤로가기(이전상태 되돌리기), 수식의 괄호 검사프린터 인쇄 대기열, 운영체제 작업 스케줄링명칭Top(또는 Peek) : 가장 마지막에 들어온 상단의 데이터Pop : 데이터 제거Push(또는 Append) : 데이터 추가front와 rear : 큐의 데이터가 위치한 머리부분을 프론트, 꼬리부분을 리어라고 한다.enqueue와 dequeue : 데이터가 들어오는 곳을 인큐, 제거되는 곳을 디큐라고 한다. * Queue를 만들 때 Array를 쓰지 않는 이유 : 데이터의 삭제 시 삭제 작업과 데이터를 앞으로 당겨주는 재배치 작업까지 총 2번을 작업.. 2025. 4. 2. 이전 1 다음