자료구조, 알고리즘 입문
자료구조와 알고리즘 인강 정리 : 연결리스트 구현
- -
연결리스트 구현
- 추상자료형 : 어떠한 데이터와 그 데이터를 연산하는 기능을 표기하는 것
ex)세탁기의 여러가지 빨래기능-빨래, 탈수, 남은시간, 배수 등(연산) 옷(데이터)
세탁기의 여러가지 기능만 나열했을 뿐 구체적인 구현방법은 나오지 않음(추상) - 연결리스트의 추상자료형 -> 자바스크립트로 표현
1. 연결리스트의 모든 데이터 출력 -> printAll()
2. 연결리스트의 모든 데이터를 제거 -> clear()
3. 인덱스 삽입 -> insertAt(index, data);
4. 마지막 데이터 뒤에 데이터를 삽입하는 기능 -> insertLast(data)
5. 인덱스 삭제 -> deleteAt(index);
6. 마지막 데이터를 삭제 -> deleteLast();
7. 원하는 인덱스에 있는 데이터 읽기 -> getNodeAt(index);
연결리스트 생성
: 연결리스트는 데이터를 담은 노드를 서로 연결하는 구조. 이를 위해 가장 먼저 노드를 만들어야 함.
1. 노드 클래스 생성
2. 클래스를 인스턴스화 했을 떄 자동으로 호출되는 생성자를 만듦.(일반적으로 생성자에서 초기화를 함)
3. 생성자의 매개변수로 data와 next를 만들고 next는 기본값을 null로 설정해준다.
(매개변수 data는 필수이지만, next는 입력하지 않는다면 null이 할당된다.)
4.자바스크립트에서 클래스 내의 변수를 프로퍼티라고 함. 생성자 내에서 data와 next 프로퍼티(변수)를 만들어 매개변수 data와 next로 초기화
5. 다른 자바스크립트 파일에서 Node클래스를 참조할 수 있도록 export
6. text.mjs 파일에서 Node 클래스를 import
7. test코드 작성 : 정수가 저장된 node1,2,3,을 만들고 next로 연결
실제 연결리스트 작성
- 인덱스 삽입 -> insertAt(index, data);
1. LinkedList 파일로 다시 이동해 LinkedList클래스 선언
2. 생성자 만들어줌(매개변수 필요x)
3. 연결리스트의 시작노드를 가리키는 head와 총저장된 노드의 수를 저장하는 count 프로퍼티를 만들어 초기화
4. 원하는 인덱스에 데이터를 삽입하는 insertAt()함수 생성 -> index=삽입할위치, data=삽입할 데이터
5. 예외처리 ( 연결리스트의 크기보다 큰 곳에 삽입하거나 음수위치에 삽인하는 경우 등과 같이 범위를 넘어가는 경우 에러처리!)
6. 새로 삽입할 노드 생성(매개변수 data를 Node의 생성자로 넘겨줘서 Node의 data를 설정)
(새로 생성한 노드 연결)
8_1. 리스트의 가장 앞부분에 삽입하는 경우는 새로 삽입하는노드가 head가 되어야함. -> 새로 생성한 노드의 next가 head를 가리키게 해주고 새로 생성한 노드를 head로 변경
8. 2. 가장 앞부분을 제외한 나머지 부분에 삽입하는 경우
: currentNode로 n -1번째 떨어진 노드로 이동 -> newNode가 n번째 노드를 가리키한다. -> currnetNode(n-1)가 새로운 노드를 가리키게 한다.
(삽입하려는 노드 바로 전까지 가기 위한 변수 생성(head에서 시작하기때문에 head로 초기화) -> 목표 인덱스 바로 전까지 next를 이용해 currentNode를 이동(목표 인덱스가 3이면 currentNode가 두번째 떨어진 노드까지 이동) -> 새로운 노드가 currentNode의 next노드를 가리킴 -> currntNode가 새로운 노드를 가리킴)
9. 새로운 노드가 삽입되었으니 if~else문 밖에 count를 하나 올려줌
10. export -> test파일에서 import
연결리스트 insertAt()함수 테스트 : 연결리스트 인스턴스화 -> 가독성을 위해 메시지 출력 -> 0부터 4까지 5개의 데이터 삽입 -> 삽입되었는지 확인을 위해 printAll함수 구현
- 연결리스트의 모든 데이터 출력 -> printAll()
- 연결리스트의 모든 데이터를 제거 -> clear()
- 마지막 데이터 뒤에 데이터를 삽입하는 기능 -> insertLast(data)
- 인덱스 삭제 -> deleteAt(index);
- 마지막 데이터를 삭제 -> deleteLast();
- 원하는 인덱스에 있는 데이터 읽기 -> getNodeAt(index);
'자료구조, 알고리즘 입문' 카테고리의 다른 글
| 자료구조와 알고리즘 인강 정리 : 큐(Queue), 큐의 구현 (0) | 2023.04.09 |
|---|---|
| 자료구조와 알고리즘 인강 정리 : 스택(Stack), 스택의 구현 (0) | 2023.04.01 |
| 자료구조와 알고리즘 인강 정리 : 배열, 연결리스트 (0) | 2023.03.31 |
| 자료구조와 알고리즘 인강 정리 : 시간복잡도 (0) | 2023.03.29 |
| 자료구조와 알고리즘 인강 정리 : 자료구조와 알고리즘이란? (0) | 2023.03.29 |
Contents
소중한 공감 감사합니다