대학생 쩡딱구리

4-4. 양방향 연결 리스트 한방향 연결 리스트는 연결 구조가 비대칭이라 임의의 노드의 삭제가 아주 비효율적이다. 즉, 아래의 단점을 갖는다. 해당 노드의 레퍼런스를 알아도 삭제에 O(n)의 시간 복잡도를 갖는다. 삭제 jjeongttakgoori.tistory.com 3-3 덱 덱 = 스택 + 큐이다! 스택과 큐를 잠깐 복습하고 보는 것을 추천한다. 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First O jjeongttakgoori.tistory.com 양방향 연결 리스트로 덱을 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다. 1. LinkedDeque 클래스 from .doubly_linke..

한방향 연결 리스트는 연결 구조가 비대칭이라 임의의 노드의 삭제가 아주 비효율적이다. 즉, 아래의 단점을 갖는다. 해당 노드의 레퍼런스를 알아도 삭제에 O(n)의 시간 복잡도를 갖는다. 삭제를 하려면 삭제할 노드뿐만 아니라 이전 노드의 레퍼런스가 필요한데, 항상 head부터 해당 노드의 이전 노드까지 이동하는 시간이 필요하다. 연결 리스트가 대칭성을 갖도록 이전 노드와 다음 노드의 레퍼런스를 갖도록 해보자. 1. 양방향 연결 리스트 양방향 연결 리스트(Doubly Linked List)는 노드들이 양방향으로 연결된 리스트로, 각 노드들은 객체(element), 이전 노드(prev), 다음 노드(next)의 레퍼런스를 저장한다. 이때 링크를 따라 특정 노드의 데이터를 접근하고 수정한다. 양방향 연결 리스트..

연결 리스트에 대한 내용은 여기에 있다. 4-1. 한방향 연결 리스트 그동안 동적 배열과 동적 배열을 기반으로 한 자료구조를 다루었다. 하지만 동적 배열엔 아래와 같은 단점이 있다. 동적 배열의 길이가 저장하는 요소의 수보다 길다. 즉 메모리 낭비가 있다. � jjeongttakgoori.tistory.com 1. 원형 연결 리스트 원형 연결 리스트(Circular Linked List)는 노드들이 원형으로 연결된 리스트이다. 위 그림과 같이 한방향 연결 리스트의 tail의 next를 head로 연결하면 원형 연결 리스트가 된다. 아래 그림도 보자. 이 그림을 통해 볼 수 있는 원형 연결 리스트의 특징은 다음과 같다. 리스트의 시작과 끝 개념이 없다. 노드 간에 순서 관계를 부여하기 위해 특정 노드의 레..

한방향 연결 리스트 내용 참고! 4-1. 한방향 연결 리스트 그동안 동적 배열과 동적 배열을 기반으로 한 자료구조를 다루었다. 하지만 동적 배열엔 아래와 같은 단점이 있다. 동적 배열의 길이가 저장하는 요소의 수보다 길다. 즉 메모리 낭비가 있다. � jjeongttakgoori.tistory.com 1. 스택 구현 스택이 뭔지 기억이 안 난다면 이 글을 참고하면 좋을 것 같다. 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), jjeongttakgoori.tistory.com 가장 먼저 들어간 것이 가장 나중에..

그동안 동적 배열과 동적 배열을 기반으로 한 자료구조를 다루었다. 하지만 동적 배열엔 아래와 같은 단점이 있다. 동적 배열의 길이가 저장하는 요소의 수보다 길다. 즉 메모리 낭비가 있다. 분할 분석 방식이 실시간 시스템에서 허용되지 않을 때가 있다. 배열의 삽입 또는 삭제 연산 비용이 O(n)으로 비싸다. 삽입, 삭제 연산이 중요할 경우 문제가 될 수 있다. 동적 배열의 이러한 단점을 해소해 삽입/연산을 빠르게 할 수 있는 선형 자료구조가 연결 리스트이다. 1. 연결 리스트란? 연결 리스트는 분산 관리 방식 자료구조이다. 이 말은 각 요소 별로 노드를 할당해 관리한다는 의미이다. 연결 리스트는 노드가(node)가 링크(link)로 연결된 순차 자료 구조로, 요소의 접근이 느리지만(O(n)) 삽입/삭제 연..

덱 = 스택 + 큐이다! 스택과 큐를 잠깐 복습하고 보는 것을 추천한다. 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), � jjeongttakgoori.tistory.com 3-2. 큐 3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되 jjeongttakgoori.tistory.com 1. 덱 위에서 썼듯 덱은 스택과 큐를 합쳐놓은..

3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), � jjeongttakgoori.tistory.com 스택에 대한 내용은 이 게시물에 있다. 1. 큐 가장 나중에 들어간 자료가 가장 먼저 나오는 스택과 달리 큐(Queue)는 FIFO(First In, First Out) 형태 자료 구조로, 가장 먼저 넣은 것이 가장 먼저 나온다. 달리 말하면 큐는 한쪽 끝에서는 자료를 넣고 한 쪽 끝에서 자료를 꺼내는 선형 자료구조를 말한다. 큐에서는 가장 최근에 저장된 값 다음에 자료가 저장되며(Enqueue), 가장 오래 ..

1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), 가장 최근에 저장된 값이 먼저 나간다(pop). 스택은 데이터를 순서대로 쌓아두었다가 가장 최근 데이터부터 봐야 할 때 쓰이는데 예를 들어 편집기의 되돌리기 기능(undo)이 스택의 예이다. 스택의 기본 연산은 아래와 같다. Operation Comment S.push(e) Top에 새로운 요소 추가 S.pop() - Top 요소를 반환하면서 제거 - 단, 스택이 비어 있으면 error 생성 S.top() - Top 요소 반환 - 스택이 비어 있으면 error 생성 S.is_e..