CodingInterview (4) 썸네일형 리스트형 [LinkedList] 단일 연결 리스트의 마지막에서 m번째 원소 이번 포스팅은 "프로그래밍 면접, 이렇게 준비한다" 라는 책 서적에 실린 면접 문제 중 '단일 연결 리스트의 마지막에서 m번째 원소' 라는 문제를 풀어볼 예정이다. 문제는 다음과 같다. Head 포인터만 갖는 단일 연결 리스트가 주어졌을 때 리스트의 맨 뒤에서 m번째 원소를 찾아내는 알고리즘을 만들어라. 이 때 시간, 공간 효율을 모두 고려해야 한다. 오류 조건의 처리에 주의하여 알고리즘을 구현해라. 여기에서 '맨 뒤에서 m번째 원소'는 m = 0일 때 리스트의 마지막 원소를 반환하는 식으로 생각한다. Step01. 아이데이션가장 처음에 떠올린 아이디어는 연결 리스트를 한 번 순회하면서 원소들을 별도의 자료구조에 저장 해두고 리스트 끝에 도달했을 때 연결 리스트의 총 길이인 N을 얻게 된다. 그리고 저장.. [LinkedList] 연결 리스트의 꼬리 포인터 이번 포스팅은 "프로그래밍 면접, 이렇게 준비한다" 라는 책 서적에 실린 면접 문제 중 '연결 리스트의 꼬리 포인터' 라는 문제를 풀어볼 예정이다. 문제는 다음과 같다. 정수를 저장하기 위한 어떤 단일 연결 리스트의 첫 번째와 마지막 원소를 가리키는 head와 tail 이라는 전역 포인터가 있다. 다음과 같은 함수 원형에 대해서 함수를 구현해라.(아래 인터페이스는 C 함수 기준이지만 우리는 Golang으로 구현 예정)- bool delete(Element *elem);- bool insertAfter(Element *elem, int data);delete 함수의 인자는 삭제할 원소다. insertAfter 함수의 두 인자는 각각 새로 추가되는 원소의 바로 앞인 이전 원소에 대한 포인터와 새 원소의 데이.. [LinkedList+Array] Golang으로 구현하는 Stack 이번 포스팅에서는 Golang으로 단일 연결 리스트 자료구조를 기반으로 Stack 자료구조를 구현하는 방법에 대해 알아보도록 하자. 해당 포스팅은 "프로그래밍 면접, 이렇게 준비한다" 라는 책 서적에 실린 면접 문제를 기반으로 한다. 문제는 다음과 같다. 스택 자료구조에 대해 논하라. 연결 리스트와 동적 배열을 써서 스택을 구현하고, Push, Pop 이라는 메소드를 구현해서 스택 인터페이스를 설계해라. 먼저 연결 리스트를 활용해서 구현해보도록 하자.1. 단일 연결 리스트를 활용한 StackStep01. 아이데이션가장 먼저 스택 자료구조에 대해 이해해야 한다. 스택은 FILO(First In, Last Out)을 기반으로 하는 자료구조이다. 즉, 가장 첫번째 넣은 원소는 가장 마지막에 나오고, 가장 마지.. [LinkedList] Golang으로 구현하는 단일 연결 리스트 이번 포스팅에서는 Golang으로 구현하는 단일 연결 리스트에 대해 알아보자. 단일 연결 리스트는 아래와 같은 구조로 되어 있는 자료구조를 의미한다. 하나의 원소 안에는 데이터와 해당 원소의 다음 원소를 가리키는 이른바 포인터 또는 레퍼런스가 담겨 있다. 위 그림 상으로 이해해보자. 첫번째 원소에 11 이라는 data를 갖고 있다. 그리고 두번째 원소를 가리키는 포인터에는 200 이라는 숫자가 들어 있다. 이 200이라는 숫자는 2번째 원소의 위치를 의미한다. 이 '원소의 위치'라는 것이 곧 메모리 주소이고 그래서 포인터라고 부르기도 한다. 우리는 위와 같은 단일 연결 리스트 자료구조를 Golang 으로 구현해보려고 한다. 앞으로의 단계를 하나씩 따라가보도록 하자.Step01. 원소(a.k.a 노드) .. 이전 1 다음
