-
Linked ListNote 2020. 10. 27. 21:37
Linked List
Linked List(연결 리스트)는 그 크기가 동적인 자료구조로,
노드(자료구조를 구성하는 요소)와 노드의 연결로 이루어진 자료 구조이다.
데이터의 구조들이 일렬로 연결된 구조이며, 각각의 노드는 ‘데이터’와 ‘다음 노드의 정보’를 가지고 있다.
연결 리스트의 맨 처음의 노드를 head, 마지막 노드를 tailtail이라고 한다.위 연결을 코드로 표현하면
LinkedList {head: Node, tail: Node, _size: 4} head: Node {value: 12, next: Node} next: Node {value: 6, next: Node} next: Node {value: 71, next: Node} next(tail): Node {value: 26, next: null}
연결 리스트의 종류
Singly linked list(일방향 연결 리스트)
리스트를 구성하는 각 노드들이 서로 다음 노드를 가리키는 정보를 가지고 있는 연결 리스트
Doubly linked list (이중 연결 리스트)
리스트를 구성하는 각 요소들이 이전의 노드와 이후의 노드에 대한 정보를 가지고 있다.
시간 복잡도(Time Complexity)
자료구조 가져오기 추가하기 삭제하기 Linked List O(n) O(1) O(1) Linked List 구현을 위한 수도코드
class Node { constructor(value) { this.value = value; this.next = null; } } class LinkedList { constructor() { this.head = null; this.tail = null; this._size = 0; } // 주어진 값을 연결 리스트 끝에 추가하는 메소드 addToTail(value) { // Node 클래스를 가지고 새 인스턴스를 생성(value 속성을 가지는) // 첫 노드인 경우(이전에 다른 노드가 없음) // head는 새 노드 // tail도 새 노드 // 사이즈 증가 // 이전에 다른 노드가 있는 경우 // 현재 tail의 next에 새 노드를 추가 // 새 노드가 새로운 tail이 된다. // size가 1 증가 // 주어진 값을 연결 찾아서 연결을 해제하는 메소드 remove(value) { // 현재 노드의 head를 새로 선언 // head의 value가 value와 같다면 // 기존 head를 다음 노드의 head로 재할당 // 현재 노드를 새로운 변수에 선언 // 아니면 // while 반복문(조건: 현재 노드의 다음 노드까지) // 현재 노드의 value가 value와 같다면 // 이전 노드가 현재 노드로 이동 // 현재 노드가 다음 노드로 이동 // 현재 노드의 value가 value와 같지 않다면 // 이전 노드, 현재 노드 둘 다 재할당되어 계속 돌아감. // size가 1 감소 // 주어진 값의 인덱스를 노드를 반환하는 메소드(없을 경우 undefined 반환) getNodeAt(index) { // 카운트를 담을 변수 선언 // 현재 노드를 담을 변수 선언 // while 반복문으로 노드를 돌면서 // 카운트가 인덱스라면 // 노드를 리턴 // 아니라면 카운트가 1증가한다. // 노드가 다음 노드로 재할당 // 반복문 끝나도 안나오면 undefined를 리턴 // 주어진 값을 가지는 노드의 존재 여부를 반환하는 메소드(boolean) contains(value) { // 현재 노드를 담을 변수 선언 // while 반복문으로 node를 돌면서 // 노드의 value가 value라면 // true를 리턴 // 아니면 노드를 다음 노드로 재할당 // 반복문 끝나도 안나오면 false를 리턴 // 주어진 값의 인덱스를 반환하는 메소드(없을 경우 -1을 반환) indexOf(value) { // 현재 노드를 담을 변수 선언 // 카운트를 담을 변수 선언 // while 반복문으로 노드를 돌면서 // 현재 노드의 value가 value와 같을 때까지 // 같을 때 카운트를 리턴 // 아니라면 카운트가 1 증가 // 노드도 다음 노드로 재할당 // 반복문 끝날 때까지 안나오면 -1를 리턴 // size를 반환하는 메소드 size() { // size를 리턴
'Note' 카테고리의 다른 글
OOP(Object Oriented Programming) (0) 2020.10.28 Hash Table (0) 2020.10.27 스택, 큐 (0) 2020.10.27 구조 분해 할당 (배열, 객체) (0) 2020.10.27 this, 화살표 (0) 2020.10.27