[데이터구조] Linked List

Linked List (연결 리스트) 개요

일련의 노드가 연결된 데이터 구조로, 각 노드는 데이터 값과 다음 노드를 가르키는 포인터로 구성된다.

그래서 다음 노드라는 것은 메모리 안 구조를 따라 가는 것이 아니라 포인터에 의해서 연결이 된다.

가장 마지막 노드는 다음 노드로 null 을 가르켜서 마지막임을 나타낸다.

 

장점

전체 데이터 구조를 재할당하거나 재구조화 하는 것 없이 리스트의 요소를 쉽게 삽입 혹은 삭제할 수 있다.

 

단점

요소에 랜덤하게 접근하는 것이 쉽지 않다.

요소에 접근하려면 O(n)의 시간 복잡도를 갖는다.

 

동작

- 삽입: 처음, 끝 혹은 주어진 인덱스에 요소를 추가한다.

- 삭제: 인덱스 혹은 값을 받아서 해당 요소를 삭제한다.

- 검색: 값을 통해서 요소를 찾는다.

 

사용

스택과 큐는 모두 연결 리스트이다.

예를 들어, 이미지 슬라이드쇼를 볼 때 사용할 수 있다.

 

Node Class (노드 클래스)

value와 next로 구성된다.

 

Linked List (연결 리스트) 구현

초기화 (constructor)

class Node {
    constructor(value) {
    	this.value = value
        this.next = null // 초기화시에는 null을 가르킴
    }
}

class LinkedList {
    constructor() {
    	this.head = null
        this.size = 0
    }
    
    isEmpty() {
    	return this.size === 0
    }
    
    getSize() {
    	return this.size
    }
}

const list = new LinkedList()

console.log(list.isEmpty()) // true
console.log(list.getSize()) // 0

 

가장 앞에 삽입 (prepend)

class LinkedList {
    // ...
    
    // O(1)
    prepend(value) {
    	const node = new Node(value)
        
        // 만약 빈 배열에 첫번째 노드를 추가했다면 헤드 포인터도 같이 넣어주어야 함
        if (this.isEmpty()) {
            this.head = node
        }
        
        // 빈 배열이 아니라면 첫번째 요소를 next로 연결한 후에 head를 추가한 요소에 할당함
        else {
            node.next = this.head
            this.head = node
        }
        
        this.size++
    }
}

list.prepend(10)
list.prepend(20)
list.prepend(30)

 

모든 요소 출력하기 (print)

class LinkedList {
    // ...
    
    print() {
    	if (this.isEmpty()) {
            console.log(`list is empty`)
        } else {
            let cur = this.head
            let listValues = ''
            
            while(cur) {
            	listValues += `${cur.value} `
                cur = cur.next
            }
            
            console.log(listValues)
        }
    }
}

const list = new LinkedList()

list.print() // list is empty

list.prepend(10)
list.print() // 10

list.prepend(20)
list.prepend(30)
list.print() // 30 20 10

 

가장 끝에 삽입 (append)

class LinkedList() {
    // ...
    
    // O(n)
    append(value) {
    	const node = new Node(value)
        
        if (this.isEmpty()) {
            this.head = node
        }
        
        // prev.next가 null이 아닐 경우 prev에 그 next를 할당함
        // prev.next가 null이 되었을 때 걔가 마지막 요소니까 prev.next에 새로 만든 요소를 연결해줌
        else {
            let prev = this.head
            while(prev.next) {
            	prev = prev.next
            }
            prev.next = node
        }
        
        this.size++
    }
}

list.append(10)
list.print() // 10

list.append(20)
list.append(30)
list.print() // 10 20 30