LimeCoding

이중 연결 리스트란?(What is Doubly linked list?) 이중 연결 리스트(doubly linked list)는 기존 단순, 원형 연결 리스트의 단점인 단방향 흐름을 2개의 링크 필드를 이용하여 양방향으로 움직일 수 있게 만든 것이 이중 연결 리스트이다. 원형 연결 리스트에 이중 연결 리스트를 결합하면 이중 원형 연결 리스트가 된다. 이중 연결 리스트는 양방향으로 움직일 수 있어 데이터 접근이 단순, 원형 연결 리스트보다 쉽고 삽입, 삭제 연산시 선행 노드에 대한 정보가 필요없다는 장점이 있다. 이중 연결 리스트의 노드는 다음과 같다. 이중 연결 리스트의 기본적인 연산은 다음과 같다. 리스트 생성 노드 삽입 노드 삭제 리스트 생성 리스트는 헤드 노드를 갖는 리스트를 생성한다. 리스트를 생..

연결 리스트를 잘 모른다면 필자가 포스팅한 내용을 보고 온다면 이해하기 편하다. 원형 연결 리스트란?(What is Circular linked list?) 원형 연결 리스트(circular linked list)는 단순 연결 리스트의 단점을 보완한 리스트이다. 단순 연결 리스트는 한 방향으로 움직이면서 그 끝이 정해져 있기 때문에 리스트를 검색할 때 항상 리스트의 처음부터 접근해야하는 단점이 있다. 또한 리스트가 순환을 요구한다면 더더욱 불리하다. 이를 해결하기 위해 단순 연결리스트의 마지막 노드가 리스트의 처음 노드를 가리키도록 만든 것이 원형 연결 리스트이다. 원형 연결 리스트는 다음과 같은 형태를 가진다. 원형 연결 리스트는 다음과 같은 기본연산을 가지고 있다. 리스트 생성 노드 삽입 노드 삭제 ..

연결 리스트란?(What is Linked List?) 연결 리스트(Linked list)란 링크로 원소들이 연결된 순차 리스트를 말한다. 연결 리스트는 순차 리스트의 삽입삭제 연산에서의 불리한 점을 보완하기 위해 만들어 졌다. 순차 리스트에서 삽입 연산을 하게 되면 중간에 데이터를 집어넣을 때 삽입될 데이터를 위해 공간을 만들어야 한다. 이때 공간을 만드는 과정에서 삽입되는 데이터 뒤에 데이터들이 자리를 옮기기 위한 연산을 취해야 하는데 이는 리스트가 가지고 있는 데이터가 크면 클수록 많은 시간이 걸린다. 삭제 연산도 삭제후 빈 공간을 채우기 위해 자리를 옮기는 과정이 필요하다. 이러한 문제점들을 해결하는 것이 연결 리스트이다. 연결 리스트를 이루는 기본적인 단위는 노드(node)이다. 노드는 데이터 ..

큐란?(What is Queue) 큐(Queue)는 데이터가 들어가는 곳과 나가는 곳이 한 곳으로 정해져있는 자료 구조를 말한다. 매표소에 사람들이 줄을 서 있으면 먼저 온 순서대로 표를 구매하게 된다. 큐는 먼저 온 데이터를 먼저 처리하는 형태를 띈다. 이를 FIFO(First-In-First-Out) 또는 LILO(Last-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 FIFO를 더 많이 사용한다. 큐에서 데이터가 삽입되는 부분을 rear라고 하고 데이터가 삭제되는 곳을 front라고 한다. rear가 가리키는 데이터는 가장 최근에 삽입된 데이터이고 front가 가리키는 데이터는 가장 먼저 삽입된 데이터이다. 큐의 연산(Queue Operation) 큐의 기본 연산은 다음과 같다. Enq..

스택이란?(What is Stack?) 우리가 식당같은 곳에 가보면 다 먹은 음식의 접시나 그릇은 위로 차곡차곡 쌓아 올리는 모습을 볼 수 있다. 설거지를 할때는 위에서부터 하나씩 꺼내어 설거지를 하게 된다. 이것이 스택이다. 스택(Stack)이란 데이터 삽입, 삭제가 한 방향에서만 이루어지는 것을 말한다. 스택은 가장 먼저 들어온 데이터는 가장 나중에 나가고 가장 나중에 들어온 데이터는 가장 먼저 나가게 된는 성질을 가지고 있다. 이를 LIFO(Last-In-First-Out) 또는 FILO(First-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 LIFO를 더 많이 사용한다. 스택은 top과 bottom이라는 2개의 포인터를 이용하여 삽입과 삭제를 제어한다. top포인터는 스택의 가장 위..

배열이란?(What is Array) 배열(array)또는 순차 리스트(sequential list)는 인덱스와 값의 쌍으로 이루어진 연속적인 메모리 위치의 집합이라고 정의할 수 있다. 배열은 인덱스와 값으로 이루어지는데 인덱스(index)는 어떤 값에 접근하기 위해 필요한 것이다. 값(value)는 배열 안에 실제로 들어가 있는 값을 의미한다. 만약 우리가 week[7] = {월, 화, 수, 목,금, 토, 일}이라는 배열을 선언한다면 요일은 배열의 값이 되고 '수'라는 값에 접근하고 싶으면 인덱스 2를 통해 접근할 수 있다. 이 부분은 c의 배열을 공부하면 배열이 어떤 식으로 작동하는지 알 수 있다. 배열은 값에 접근할 때 O(1)의 시간 복잡도를 갖는다. 즉, 배열은 어떤 값에 접근하던지 모두 동일한..