이중 연결리스트란? 단순 연결리스트의 선행 노드가 찾기 힘들다는 점을 보완한 리스트 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트 노드의 left link와 right link가 각각 다른 노드의 오른쪽 링크와 왼쪽 링크를 연결짓는다. 헤드부분도 노드로 이루어져 있다. 단점은 공간을 많이 차지하고 코드가 복잡하다. ※ 헤드노드란? 헤드노드는 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드이다. 따라서 헤드 포인터와의 구별이 필요하며 리스트가 공백상태라면 헤드 노드만 존재하는 상태이다. 이때 헤드노드의 left link는 right link를 가리키며 right link는 left link를 가리키는 상태이다. 노드 구조체 typedef int eleme..

원형 연결리스트란? 원형 연결리스트는 리스트의 마지막 노드의 링크가 첫번째 노드를 가리키는 연결리스트를 말한다. 한 노드에서 다른 모든 노드로의 접근이 가능하다. 헤드포인터가 마지막 노드를 가리키게 끔 구성하면, 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비하여 용이하다. 2022.12.11 - [📚 자료구조 및 알고리즘/리스트] - [자료구조] 리스트(List)란? [자료구조] 리스트(List)란? 리스트란? 리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료구조이다. 순서는 논리적으로 지켜지며, 원소가 저장되는 물리적인 위치는 상관하지 않는다. 배열을 이용한 리스트를 linerate.tistory.com 원형 연결리스트 특성 위 그림에서 데이터값 8을 가지는 노드는..

연결리스트란? 개념은 기존의 리스트와 동일하지만 각 데이터 항목들을 노드(node)라고 하는 곳에 분산하여 저장한다는 점에서 차이가 있다. 노드는 데이터 필드와 링크 필드로 구성된다. 데이터 필드: 리스트의 원소, 즉 데이터 값을 저장하는 곳 링크 필드: 다른 노드의 주소값을 저장하는 장소 (포인터) 리스트의 개념은 링크 참고 https://linerate.tistory.com/118 [자료구조] 리스트(List)란? 리스트란? 리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료구조이다. 순서는 논리적으로 지켜지며, 원소가 저장되는 물리적인 위치는 상관하지 않는다. 배열을 이용한 리스트를 linerate.tistory.com 연결리스트 장단점 장점 삽입, 삭제가 보다 용이하다. 연속된 메모리 공..

리스트란? 리스트는 배열과 달리 원소들 간의 논리적인 순서를 위한 자료구조이다. 순서는 논리적으로 지켜지며, 원소가 저장되는 물리적인 위치는 상관하지 않는다. 배열을 이용한 리스트를 구현하면 논리적인 순서를 지키기 위해 시간복잡도가 늘어난다. 일반적으로는 포인터 변수를 통한 연결 리스트를 이용한다. 배열을 이용한 리스트 구현 배열을 사용하여 리스트를 구현할때는 삽입과 삭제할 시 데이터의 이동이 많이 발생하기 때문에 시간복잡도가 증가하지만, 인덱스로 접근하는 속도는 연결리스트에 비해 빠른 편이다. 하지만 배열은 공간이 일정하기 때문에 계속 값이 늘어나는 데이터를 사용할 때에는 일반적으로 연결리스트를 사용한다. 하지만 구조를 이해하기 쉽게 지금은 배열을 이용하여 리스트를 구현해보도록 하겠다. 리스트 ADT ..

배열과 연결리스트는 순차적으로 데이터를 저장한다는 점에서 비슷하다. 두 자료구조에 대해서 알아보도록 하자. 배열(Array) 배열은 논리적 저장순서와 물리적 저장순서라 일치하는 자료구조이다. 즉 인덱스(index)로 해당 원소에 접근이 가능하다. 따라서 원소의 인덱스 값을 이용하면 O(1)에 해당 원소에 접근 할 수 있다. 그러나 삭제 또는 삽입의 과정에서 추가적인 시간이 소요될 수 있다. 예를 들어 아래와 같은 상황에서 배열의 첫번째 자리(Arr[0])에 새로운 원소를 추가한다고 하자. 위와 같은 상황에서 Arr[0] 에 데이터 10을 추가하기 위해서는, Arr[0] 부터 Arr[4] 까지 모든 원소가 한 칸 씩 오른쪽으로 이동하게 된다. 즉, 원소를 삽입할 때 최악의 경우 모든 원소들을 1씩 옮기는 ..