단일 연결리스트(Singly Linked List)

단일 연결리스트의 간략한 구조 (Colt Steele 강좌의 자료화면)

단일 연결리스트(Singly Linked List)

단일 연결리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 선형 데이터 구조이다.
각 노드는 다음 노드만을 가리키며 (단방향), 이전 노드로는 접근할 수 없다.
 
장점:
1. 동적 크기 - 메모리를 효율적으로 사용
2. 삽입/삭제가 배열보다 효율적
3. 메모리 할당이 유연함
 
단점:
1. 특정 인덱스로의 접근이 O(n)
2. 이전 노드로 접근 불가
3. 추가 메모리 공간 필요 (다음 노드 포인터)

 

필수 구현 메서드

 

• push() - 끝에 추가
• pop() - 끝에서 삭제
• shift() - 앞에서 삭제
• unshift() - 앞에 추가
• get() - 조회
• set() - 수정
• insert() - 중간 삽입
• remove() - 중간 삭제

 

위 목록은 단일 연결 리스트를 구현할 때 필수적으로 구현해야 하는 메서드들이다. 외에도 부가적인 메서드들이 있지만 그것들은 사용 편의 목적이므로 자료구조의 핵심기능과 직접적인 연관은 없다. 

 

* 맨 아래에 내가 따로 주석을 단 코드가 존재함.

 

/**
 * 단일 연결리스트(Singly Linked List)
 * 
 * 데이터 구조의 특징:
 * 1. 선형 데이터 구조로, 각 노드가 다음 노드를 가리키는 포인터를 가짐
 * 2. Head(시작점)에서 Tail(끝점)까지 단방향으로만 접근 가능
 * 3. 메모리에 연속적으로 저장되지 않음
 * 
 * 시간 복잡도:
 * - 접근: O(n)
 * - 검색: O(n)
 * - 삽입: O(1) - 위치를 알고 있는 경우
 * - 삭제: O(1) - 위치를 알고 있는 경우
 * 
 * 장점:
 * - 동적 크기 조절 가능
 * - 삽입/삭제가 효율적
 * - 메모리 사용이 유연함
 * 
 * 단점:
 * - 임의 접근 불가 (인덱스로 직접 접근 불가)
 * - 이전 노드로 이동 불가
 * - 추가 메모리 필요 (포인터)
 */

// 노드 클래스: 연결리스트의 각 요소를 표현
class Node {
    constructor(val) {
        this.val = val;      // 노드가 저장하는 값
        this.next = null;    // 다음 노드를 가리키는 포인터
    }
}

// 단일 연결리스트 클래스
class SinglyLinkedList {
    constructor() {
        this.head = null;    // 리스트의 첫 번째 노드
        this.tail = null;    // 리스트의 마지막 노드
        this.length = 0;     // 리스트의 전체 길이
    }

    /**
     * 리스트 끝에 새로운 노드를 추가
     * 시간 복잡도: O(1)
     * @param {any} val - 새로운 노드에 저장할 값
     * @returns {SinglyLinkedList} 업데이트된 연결리스트
     */
    push(val) {
        const newNode = new Node(val);
        if (!this.head) {
            // 리스트가 비어있는 경우
            this.head = newNode;
            this.tail = this.head;
        } else {
            // 리스트에 노드가 있는 경우
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }

    /**
     * 리스트의 마지막 노드를 제거
     * 시간 복잡도: O(n) - 마지막 이전 노드를 찾아야 함
     * @returns {Node|undefined} 제거된 노드 또는 undefined
     */
    pop() {
        if (!this.head) return undefined;
        
        let current = this.head;
        let newTail = current;
        
        // 마지막 노드와 그 이전 노드를 찾음
        while (current.next) {
            newTail = current;
            current = current.next;
        }
        
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        
        if (this.length === 0) {
            // 모든 노드가 제거된 경우
            this.head = null;
            this.tail = null;
        }
        
        return current;
    }

    /**
     * 리스트의 첫 번째 노드를 제거
     * 시간 복잡도: O(1)
     * @returns {Node|undefined} 제거된 노드 또는 undefined
     */
    shift() {
        if (!this.head) return undefined;
        
        const currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        
        if (this.length === 0) {
            this.tail = null;
        }
        
        return currentHead;
    }

    /**
     * 리스트의 시작에 새로운 노드를 추가
     * 시간 복잡도: O(1)
     * @param {any} val - 새로운 노드에 저장할 값
     * @returns {SinglyLinkedList} 업데이트된 연결리스트
     */
    unshift(val) {
        const newNode = new Node(val);
        if (!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

    /**
     * 특정 인덱스의 노드를 반환
     * 시간 복잡도: O(n)
     * @param {number} index - 찾고자 하는 노드의 인덱스
     * @returns {Node|null} 찾은 노드 또는 null
     */
    get(index) {
        if (index < 0 || index >= this.length) return null;
        
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }

    /**
     * 특정 인덱스의 노드 값을 변경
     * 시간 복잡도: O(n)
     * @param {number} index - 변경하고자 하는 노드의 인덱스
     * @param {any} val - 새로운 값
     * @returns {boolean} 변경 성공 여부
     */
    set(index, val) {
        const foundNode = this.get(index);
        if (foundNode) {
            foundNode.val = val;
            return true;
        }
        return false;
    }

    /**
     * 특정 인덱스에 새로운 노드를 삽입
     * 시간 복잡도: O(n)
     * @param {number} index - 삽입할 위치의 인덱스
     * @param {any} val - 새로운 노드에 저장할 값
     * @returns {boolean} 삽입 성공 여부
     */
    insert(index, val) {
        if (index < 0 || index > this.length) return false;
        if (index === this.length) return !!this.push(val);
        if (index === 0) return !!this.unshift(val);
        
        const newNode = new Node(val);
        const prev = this.get(index - 1);
        const temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }

    /**
     * 특정 인덱스의 노드를 제거
     * 시간 복잡도: O(n)
     * @param {number} index - 제거할 노드의 인덱스
     * @returns {Node|undefined} 제거된 노드 또는 undefined
     */
    remove(index) {
        if (index < 0 || index >= this.length) return undefined;
        if (index === 0) return this.shift();
        if (index === this.length - 1) return this.pop();
        
        const previousNode = this.get(index - 1);
        const removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;
    }

    /**
     * 리스트의 순서를 뒤집음
     * 시간 복잡도: O(n)
     * @returns {SinglyLinkedList} 순서가 뒤집힌 연결리스트
     */
    reverse() {
        let node = this.head;
        this.head = this.tail;
        this.tail = node;
        let next;
        let prev = null;
        
        for (let i = 0; i < this.length; i++) {
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return this;
    }

    /**
     * 리스트의 모든 값을 배열로 출력 (디버깅용)
     */
    print() {
        const arr = [];
        let current = this.head;
        while (current) {
            arr.push(current.val);
            current = current.next;
        }
        console.log(arr);
    }
}

 

 

용례

// 연결리스트 생성 및 기본 조작 예시
const shoppingList = new SinglyLinkedList();

// 1. push로 초기 아이템 추가
console.log("\n1. 쇼핑 리스트 만들기");
shoppingList.push("사과");
shoppingList.push("바나나");
shoppingList.push("오렌지");
shoppingList.print(); // ['사과', '바나나', '오렌지']

// 2. unshift로 맨 앞에 아이템 추가
console.log("\n2. 맨 앞에 우유 추가");
shoppingList.unshift("우유");
shoppingList.print(); // ['우유', '사과', '바나나', '오렌지']

// 3. 특정 위치에 아이템 삽입
console.log("\n3. 인덱스 2에 딸기 추가");
shoppingList.insert(2, "딸기");
shoppingList.print(); // ['우유', '사과', '딸기', '바나나', '오렌지']

// 4. get으로 특정 위치의 아이템 확인
console.log("\n4. 인덱스 2의 아이템 확인");
const item = shoppingList.get(2);
console.log("인덱스 2의 아이템:", item.val); // '딸기'

// 5. set으로 아이템 변경
console.log("\n5. 바나나를 포도로 변경");
shoppingList.set(3, "포도");
shoppingList.print(); // ['우유', '사과', '딸기', '포도', '오렌지']

// 6. remove로 특정 위치의 아이템 제거
console.log("\n6. 인덱스 2의 아이템(딸기) 제거");
shoppingList.remove(2);
shoppingList.print(); // ['우유', '사과', '포도', '오렌지']

// 7. pop으로 마지막 아이템 제거
console.log("\n7. 마지막 아이템 제거");
const lastItem = shoppingList.pop();
console.log("제거된 아이템:", lastItem.val);
shoppingList.print(); // ['우유', '사과', '포도']

// 8. shift로 첫 번째 아이템 제거
console.log("\n8. 첫 번째 아이템 제거");
const firstItem = shoppingList.shift();
console.log("제거된 아이템:", firstItem.val);
shoppingList.print(); // ['사과', '포도']

// 9. reverse로 리스트 순서 뒤집기
console.log("\n9. 리스트 순서 뒤집기");
shoppingList.reverse();
shoppingList.print(); // ['포도', '사과']

// 실제 활용 예시: 실행 취소(undo) 기능 구현
class UndoStack {
    constructor() {
        this.actions = new SinglyLinkedList();
    }

    addAction(action) {
        this.actions.push(action);
    }

    undo() {
        return this.actions.pop()?.val;
    }

    printHistory() {
        console.log("작업 기록:");
        this.actions.print();
    }
}

// Undo 스택 사용 예시
console.log("\n실제 활용 예시: Undo 스택");
const undoStack = new UndoStack();

undoStack.addAction("텍스트 입력");
undoStack.addAction("이미지 삽입");
undoStack.addAction("폰트 변경");

console.log("현재 작업 기록:");
undoStack.printHistory();

console.log("\nUndo 실행:");
const undoAction = undoStack.undo();
console.log("취소된 작업:", undoAction);
undoStack.printHistory();

// 순회 예시: 리스트의 모든 값 합계 구하기
const numberList = new SinglyLinkedList();
numberList.push(10);
numberList.push(20);
numberList.push(30);
numberList.push(40);

const getSum = (list) => {
    let sum = 0;
    let current = list.head;
    while (current) {
        sum += current.val;
        current = current.next;
    }
    return sum;
};

console.log("\n숫자 리스트 합계 구하기:");
numberList.print();
console.log("합계:", getSum(numberList)); // 100

 

 

 

 

 

----

 

직접 타이핑하고 주석을 작성한 코드

class Node {

	// 단일연결리스트를 구성하는 노드. val과 next 속성을 가진다.
	constructor(val) {
		this.val = val;
		this.next = null;
	}
}


class SinglyLinkedList {
	// 헤드, 테일, 길이 속성을 기본으로 가짐
	
	constructor() {
		this.head = null;	// 리스트의 첫 노드
		this.tail = null;	// 리스트의 끝 노드
		this.length = 0;	// 리스트의 길이(노드 개수)
	}

	/*	리스트의 마지막에 노드를 추가하는 메서드	*/
	push(val) {
		const newNode = new Node(val); // 새 노드 생성
		if (!this.head) {	//헤드가 없는 경우, 즉 리스트가 비어있는 경우
			this.head = newNode;	// 헤드와 테일을 신규 노드로 설정
			this.tail = this.head;
		} else {
			// 리스트에 노드가 존재하는 경우
			this.tail.next = newNode; // 기존 테일의 넥스트 속성에 신규 테일을 할당하는 코드
			this.tail = newNode; // 그렇게 하고 신규 테일을 현재 테일로 재할당.

			// "기존 테일은 그 직전 노드의 넥스트로 참조돼 있으므로
			// 기존 노드와의 연결성이 사라진 것이 아님. 단지 테일 변수로부터의 참조를 잃었을 뿐." 
		}
		this.length++;
		return this;  // 변경된 리스트 객체 전체를 다시 반환.
	}

	/*	리스트의 마지막 노드를 반환하는 메서드(해당 노드 제거됨)	*/
	pop() {
		if(!this.head) return undefined // 리스트가 빈 경우. 언디파인드 반환

		let current = this.head;	// 맨 앞 노드가 현재
		let newTail = current;	// 맨 앞 노드를 새로운 테일로

		 // 다음 노드가 존재하지 않을 때까지 순회
		while (current.next) {
			newTail = current;	// next속성을 가지고 있는, length -2 노드
			current = current.next; // 다음 노드를 현재 노드에 할당함으로서 마지막 노드로 이동.

			// 결국 newTail은 기존 리스트에서 가장 끝 노드의 직전노드가 할당됨.
			// current는 더이상 next를 가지고 있지 않은 기존 테일노드가 됨.
		}

		this.tail  = newTail; // 뉴테일을 기존 테일로 할당
		this.tail.next = null;	// 마지막 노드가 됐으므로 넥스트를 null로 설정
		this.length--;	// 길이 감소

		if (this.length === 0) {	//리스트가 비었다면
			this.head = null;
			this.tail = null;
		}

		return current;	// 기존 테일 노드(next속성이 없던 노드)가 반환됨.
	}

	/*	리스트의 맨 앞에 있는 노드를 반환하는 메서드(해당 노드 제거됨)	*/
	shift() {
		if(!this.head) return undefined; // 리스트가 빈 경우.
		// 노드가 존재하는 경우
		const currentHead = this.head;	// 기존 헤드를 반환할 변수에 할당
		this.head = currentHead.next;  	// 기존 헤드의 다음 노드를 기존 헤드에 할당.(헤드변경)
		this.length--;

		if (this.length === 0) {
			this.tail = null;
			// 노드가 하나밖에 없었다면 this.next가 null이었을 것이므로 헤드까지 널 할당할 필요 없음
		}
		return currentHead;
	}

	/*	맨 앞에 노드를 추가하는 메서드	*/
	unshift(val) {
		const newNode = new Node(val); // 노드 생성
		if (!this.head) {	// 리스트가 비었다면 헤드와 테일을 모두 신규노드로 설정
			this.head = newNode;
			this.tail = this.head;
		} else {	// 기존 노드가 존재한다면 신규 노드의 넥스트를 기존 헤드로 참조하고 헤드에 신규노드를 할당함.
			newNode.next = this.head;
			this.head = newNode;
		}
		this.length++;
		return this;
	}

	/*	인덱스를 통해 리스트의 노드의 값을 반환하는 인덱스(해당 노드 제거 X)	*/
	get(index) {
		if (index < 0 || index >= this.length) return null; // 범위 이상 시 널 리턴


		let current = this.head;
		for (let i = 0; i < index; i++) {
			current = current.next; // 헤드에서 시작하여 계속해서 테일 쪽으로 이동
		}
		return current;
	}

	/*	인덱스를 통해 해당 노드의 값은 지정하는 메서드	*/
	set(index, val) {
		const foundNode = this.get(index); //get을 사용해서 노드 확인
		if (foundNode) {	// 반환된 노드가 falsy(여기서는 null)가 아니라면
			foundNode.val = val;
			return true;
		}
		return false;
	}
			/*
			이렇게 해도 되지만 겟을 사용하는 편이 나음.
			set(index, val) {
				if (index < 0 || index >= this.length) return null;

				let current = this.head;
				for (let i = 0; i < index; i++) {
					current = current.next
				}
				current.val = val;
				return this;
			}
			*/

	/*	리스트 중간에 노드를 끼워넣는 메서드		*/
	insert(index, val) {
		if(index < 0 || index > this.length) return false;
		// >=를 쓰지 않은 것은 맨 뒤에 추가될 수도 있기 때문임. 이는 일반적인 push와 동일.

		if (index === this.length) return !!this.push(val) // 맨 뒤에 push하고 true반환.
		if (index === 0) return !!this.unshift(val);

		const newNode = new Node(val);
		const prev = this.get(index-1); // 직전 노드 획득
		const temp = prev.next; // 삽입할 위치에 원래 존재하던 노드 보관

		prev.next =  newNode;	// 직전 노드의 넥스트에 삽입할 노드 참조
		newNode.next = temp;	// 삽입할 노드의 넥스트에 기존 노드 연결
		this.length++;

		return true;
	}

	/*	특정 인덱스의 노드 제거	*/
	remove(index) {
		if (index < 0 || index >= this.length) return null;
		if (index === 0 ) return this.shift();
		if (index === this.length - 1 ) return this.pop();

		const prevNode = this.get(index - 1);
		const removed = prevNode.next;

		prevNode.next = removed.next;	// 직전 노드의 넥스트를 제거대상 노드의 넥스트로 할당.

		this.length--;
		return removed;	// 제거된 노드 반환

	}

	/*	리스트의 방향 바꾸기. 헤드가 테일로 테일이 헤드로	*/
	reverse() {
	    let node = this.head;    // 현재 작업할 노드를 헤드로 시작
	    this.head = this.tail;   // 헤드와 테일을 먼저 교체
	    this.tail = node;        // 기존 헤드를 테일로 설정

	    let next;                // 다음 노드를 임시 저장할 변수
	    let prev = null;         // 이전 노드를 저장할 변수 (최초 테일의 next는 null이어야 함)

	    for (let i = 0; i < this.length; i++) {
	        // 1단계: 다음 노드 임시 저장
	        next = node.next;    // 현재 노드의 다음 노드를 임시 저장
	                            // (이렇게 안하면 연결이 끊어져서 다음 노드를 찾을 수 없음)

	        // 2단계: 현재 노드의 방향 바꾸기
	        node.next = prev;    // 현재 노드가 이전 노드를 가리키도록 변경
	                            // (방향을 반대로 바꾸는 핵심 동작)

	        // 3단계: 다음 반복을 위한 변수 이동
	        prev = node;         // 다음 반복에서 현재 노드가 이전 노드가 됨
	        node = next;         // 다음 반복에서 임시 저장했던 다음 노드가 현재 노드가 됨
	    }
	    return this;
	}

}