자료구조와 알고리즘 ft. 수업/알고리즘 정리

2. 연결 리스트

3. 연결리스트 1. 연결리스트의 소개 - 연결 리스트란? 연결리스트는 동적으로 크기가 변할 수 있고, 삭제나 삽입시에 데이터 이동이 필요없는 연결된 표현(linked representation)(데이터와 링크로 구성, 링크가 데이터들을 연결하는 역할을 함)임. 연결 리스트(linked list): 물리적으로 흩어져 있는 자료들을 서류 연결하여 하나로 묶는 방법 장점: 삽입, 삭제시 데이터 이동이 필요없음, 데이터 저장 공간을 동적으로 생성할 수 있음 단점: 연산의 구현이나 사용방법이 배열에 비해 복잡하여 오류 발생 가능성이 높음, 링크 필드를 위한 추가 공간 필요 - 연결리스트의 구조 노드(node) = 데이터 필드(data field, 저장하고 싶은 데이터) + 링크 필드(link field, 다른 ..

1. 리스트

1. 리스트의 추상 자료형 - 리스트의 개념 리스트 : 목록 형태로 이뤄진 데이터 형식 노드 (Node, 마디) : 리스트의 목록을 이루는 개별 요소 첫 번째 노드를 헤드 (Head, 머리) 라고 부르고 마지막 노드를 테일 (Tail, 꼬리) 이라고 부른다 리스트의 길이는 헤드부터 테일까지 이르는 노드 개수와 같다 ADT는 자료구조가 갖춰야 할 일련의 연산 리스트도 갖춰야 할 연산이 있는데 Append : 리스트에 노드를 추가하는 연산 Insert : 노드 사이에 노드를 삽입하는 연산 Remove : 노드를 제거하는 연산 GetAt : 특정 위치에 있는 노드를 반환하는 연산 - 리스트의 구현 리스트는 배열과 연결 리스트를 이용하여 구현할 수 있음 배열로 구현된 리스트 장점 구현이 간단 속도가 빠름 단점 ..