[자료구조] 단일 연결리스트 (Singly Linked List)

yeonhwan619·2023년 8월 24일
자료구조

자료구조

목록 보기
1/6

단일 연결리스트란?

단일 연결리스트란 Node 라는 매우 간단한 자료 단위가 선형적으로 연결되어있는 자료구조를 말한다. Node는 value와 자기 자신의 다음 번째의 Node를 가리킬 수 있는 포인터인 next를 값으로 가질 수 있고 단일 연결 리스트는 이 Node들이 차례로 연결되어있는 형태를 가지고 있다.

단일 연결리스트는 언뜻보면 배열과 비슷하다고 느껴질 수 있지만 index를 사용할 수 없다는 차이점이 존재한다. 배열은 값 하나 하나에 index를 부여하여 자료구조를 탐색하지만, 단일 연결리스트는 따로 index를 만들어내지 않고 Node의 next 값들을 통해서만 탐색할 수 있다.

위와 같은 단일 연결리스트의 특징은 배열보다 빠른 속도로 값을 삽입하거나 삭제하는데 뛰어난 성능을 보일 수 있도록 해준다. 하지만 배열과 달리 index를 사용하지 못하므로 반드시 traverse를 통해서만 원하는 값으로 이동할 수 있다는 단점을 지니고 있다.

단일 연결리스트 자료구조에는 Node들의 연결을 저장하므로 다음과 같은 정보를 가지고 있다.

  1. head : 연결리스트의 시작 Node의 참조값
  2. tail : 연결리스트의 끝 Node의 참조값
  3. length : 연결리스트의 길이

단일 연결리스트 만들기

단일 연결리스트를 만들기 위해서 간단하게 Node 클래스를 먼저 생성한다. Node를 생성한다음 이 Node들을 연결을 담아줄 수 있는 단일 연결리스트 클래스를 생성하면 단일 연결리스트를 만들어낼 수 있다.


class Node {
  constructor(value, next=null) {
  	this.value = value;
    this.next = next;
  }
}

class SinglyLinkedList {
	
  constructor(head=null, tail=null, length=0) {
  	this.head = head;
    this.tail = tail;
    this.length = length;
  }

}

// Node 생성하기
const Node1 = new Node("a"); // {value: "a", next: null}
const Node2 = new Node("b"); // {value: "b", next: null}
const Node3 = new Node("c"); // {value: "c", next: null}

// Node 연결하기
Node1.next = Node2; // {value: "a", next: Node2}
Node2.next = Node3; // {value: "b", next: Node3}

// 연결리스트 생성하기
const SLL = new SinglyLinkedList(Node1, Node3, 2);
// {head: Node1, tail: Node3, length: 3}
// a -> b -> c

단일 연결리스트 메소드

연결리스트를 만들었으니 연결리스트를 사용하기 위한 메소드들을 살펴보고 작성해보자. 연결리스트에 관련된 메소드들은 대표적으로 다음과 같다.

  1. push : 연결리스트의 마지막에 Node를 추가한다.
  2. pop : 연결리스트의 마지막 Node를 제거한다.
  3. shift : 연결리스트의 첫부분에 Node를 제거한다.
  4. unshift : 연결리스트의 첫부분의 Node를 추가한다.
  5. get : 원하는 위치의 Node의 값을 얻는다.
  6. set : 원하는 위치의 Node의 값을 변경한다.
  7. insert : 원하는 위치에 Node를 삽입한다.
  8. remove : 원하는 위치의 Node를 제거한다.
  9. traverse : 연결리스트를 정방향으로 순회하며 값을 반환한다.
  10. reverse : 연결리스트의 연결을 역방향으로 변경한다.

1. push (value)

배열의 push 메소드와 동일하게 값을 전달받아 Node를 생성한 후 연결리스트의 마지막에 삽입한다. 전달받은 값으로 Node를 새로 생성하고 tail의 값을 그 Node로 교체한뒤 length 를 하나 늘려준다. 만일 SLL이 비어있는 상태라면 가장 처음에 Node를 추가하고 head, tail, length의 값을 채운다.

1. value: Node의 값
return : 새롭게 추가한 Node

// 1. 리스트가 비어있을 때
// 2. 리스트가 비어있지 않을 때

push(value) {
	const newNode = new Node(value);
    // 1)
	if(!this.head) {
      this.head = newNode;
      this.tail = newNode;
      this.length++;
      return this;
    }
    // 2)
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }

...

SLL.push("d");
// newNode : {value: "d", next: null}
// {head: Node1, tail: newNode, length: 4}
// a -> b -> c -> d

2. pop

단일 연결리스트의 마지막 Node를 제거하고 SLL을 반환하도록 한다. 만일 연결리스트가 비어있다면 어떠한 Node도 제거하지 않고 null을 반환하고, 비어있지 않다면 next 포인터를 순회하여 마지막 tail의 값을 제거하고 반환한다. 이 때, tail 과 length의 값을 알맞게 변경해준다.

return : 제거된 Node

// 1. 리스트가 비었을 때
// 2. Node가 하나일 때
// 3. Node가 다수일 때
    
pop() {
    // 1)
    if(!this.tail || !this.head) return null;
        
    // 순회를 위한 포인터 선언
    let prevNode = this.head;
    let curNode = this.head.next;
        
    // 3)
    while(curNode) {
       if(!curNode.next) {
         this.tail = prevNode;
         this.length--;
         return curNode;
       }
       prevNode = curNode;
       curNode = curNode.next;
   }
      
   // 2)
   this.head = null;
   this.tail = null;
   this.length--;
   return prevNode;
}



...


SLL.pop();
// {value: "c", next: null}
// {head: Node1, tail: Node2, length: 2}
// a-> b

3. shift

단일 연결리스트의 첫 번째에 위치해 있는 Node를 제거한 후 그 값을 반환하도록 한다. 값이 존재하지 않으면 null을 반환한다. 제거한 후 length 와 tail을 현재 리스트의 상태에 알맞게 변경한다.

return : 제거된 Node

// 1. 리스트가 비었을 때
// 2. 리스트가 비어있지 않을 때
	// 2-1. Node가 하나일 때
    
shift() {
  // 1)
  if(!this.head) return null;
  
  // 2)
  const prevHead = this.head;
  this.head = this.head.next;
  this.length--;
  
  // 2-1)
  if(!this.length) this.tail = null; 
  return prevHead;
}



...


SLL.shift();
// {value: "a", next: Node2} (리스트에서 제거는 했으나, 제거한 Node의 연결을 끊어주지는 않았다)
// {head: Node2, tail: Node3, length: 2}
// b-> c

4. unshift (value)

value를 전달 받아 새로운 Node를 생성하고 리스트의 첫 부분에 삽입한다. 만약 리스트가 비어있다면 그대로 Node를 head에 할당하고 그렇지 않다면 현재 존재하는 head와 교체하도록 한다.

1. value: Node의 값
return : 새롭게 생성한 Node

// 1. 리스트가 비었을 때
// 2. 리스트가 비어있지 않을 때
    
unshift(value) {
	const newNode = new Node(value);
    // 1)
  	if(!this.head) {
    	this.head = newNode;
      	this.tail = newNode;
      	this.length++;
      	return this.head;
    }
  	// 2)
  	newNode.next = this.head;
  	this.head = newNode;
  	this.length++;
  	return this.head;
}	



...


SLL.unshift("z");
// {value: "z", next: Node1}
// {head: newNode, tail: Node3, length: 4}
// z -> a -> b -> c

5. get(index)

index를 전달받아 해당 위치에 존재하는 Node를 반환한다. 배열과 다르게 연결리스트에서는 index가 존재하지 않기 때문에 순회를 통해서 값을 찾아 반환해야한다.

1. index : Node를 찾을 위치 값
return : 해당 index에 위치한 Node

// 1. 리스트가 비었을 때
// 2. index 에 Node가 존재하지 않을 때
// 3. index 에 Node가 존재할 때
    
get(index) {
	let curNode = this.head;
    // 1), 2)
  	if(!curNode || this.length <= index) return null;
  	
    // 3)
  	let count = 0;
  	while (count < index) {
    curNode = curNode.next;
    count++;
    }
  	return curNode;
}	



...


SLL.get(2);
// {value: "b", next: Node3}
// a -> b -> c

6. set(index, value)

전달받은 index위치에 존재하는 Node의 값을 value로 변경한다. 이전에 작성해두었던 get 메소드를 통해서 위치를 쉽게 찾아 해당 위치에 삽입할 수 있다.

1. index : 변경할 위치 index
2. value : 변경할 값
return : 변경된 Node

// 1. Node가 존재할 경우
// 2. Node가 존재하지 않을 경우


set(index, value) {
	const foundNode = this.get(index);
  	// 1)
  	if(foundNode) {
      foundNode.value = value;
      return foundNode;
    }
    // 2)
  	return null;
}	



...


SLL.set(2, "B");
// {value: "B", next: Node3}
// a -> B -> c

7. insert(index, value)

전달 받은 value를 통해 새로운 Node를 생성해 전달 받은 index위치에 해당 Node를 삽입한다. 새로운 Node와 함께 해당위치에 존재하던 이전의 Node들의 연결을 바꾸어 주어야한다. index는 현재 존재하는 리스트의 length를 넘거나 0 미만이 될 수 없다. 이전에 작성해두었던 unshift, push, get 메소드들을 이용해 해결할 수 있다.

1. index: 삽입할 위치
2. value: 새롭게 생성할 Node의 값
return : 새롭게 생성된 Node

// 1. index가 0일 때
// 2. index가 length 일 때
// 3. index가 0~length 사이 일 때
    
insert(index, value) {
  	if(index < 0 || index > this.length) return null;
 	
    // 1)
  	if(index === 0) {
    	this.unshift(value);
    }
    // 2)
  	if(index === this.length) {
    	this.push(value);
    }
  	// 3)
  	const newNode = new Node(value);
	const beforeIndexNode = this.get(index - 1);
	newNode.next = beforeIndexNode.next;
  	beforeIndexNode.next = newNode;
  	this.length++;
  	return newNode;
}	



...


SLL.insert("ㄱ", 1);
// {value: "ㄱ", next: Node2}
// a-> ㄱ -> b -> c

8. remove(index)

index를 전달받아 해당 위치에 존재하는 Node를 제거한다. index는 insert와 동일하게 0 미만이 될 수 없고, 현재 length 이상을 벗어날 수 없다. 작성해두었던 shift, pop, get 메소드를 통해서 쉽게 해결할 수 있다.

1. index: 제거할 Node의 위치
return : 제거한 Node

// 1. index가 0일 때
// 2. index가 length 일 때
// 3. index가 0~length 사이 일 때

remove(index) {
	if(index < 0 || index > this.length) return null;
	// 1)
	if(index === 0) {
    	this.shift();
    }
  	// 2)
  	if(index === this.length) {
    	this.pop();
    }
  	// 3)
  	const beforeIndexNode = this.get(index - 1);
  	const removed = beforeIndexNode.next;
  	beforeIndexNode.next = beforeIndexNode.next.next;
  	this.length--;	
  	return removed;
}

...

SLL.remove(1);
// {value: "b", next: Node3}
// a-> c

9. traverse

단일 연결리스트를 모두 순회하여, 순회한 값들을 배열에 담아 return한다.

return: 연결리스트의 Node들의 값을 담은 배열

traverse() {
	const result = [];
  	
  	let curNode = this.head;
  	while(curNode) {
    	result.push(curNode.value);
    	curNode = curNode.next;
    }
  	return result;

}

...

SLL.traverse();
// ["a","b","c"]
// a -> b -> c

10. reverse()

현재 작성된 단일 연결리스트의 연결 순서를 역방향으로 뒤집는다. 원본 리스트를 변경하며 변경된 리스트의 값을 반환한다.

return: 역방향으로 연결된 연결리스트

reverse() {
  	// 변경을 시작할 기준 node
  	let node = this.head;
    // 기준 node의 이전 node와 다음 node를 추적하기 위한 변수
  	let next = null;
  	let prev = null;
 	// 변경을 시작하기 전에 head 와 tail의 순서를 바꾸어준다.
  	this.head = this.tail;
  	this.tail = node;
  	
  	while(node) {
    	next = node.next;
      	node.next = prev;
      	prev = node;
    	node = next;
      
      // node 값을 기준으로 하나 하나 순회하며 현재 node의 next 연결을 끊는다.
      // 그 후 역순이기 때문에 이전 순회에 저장했던 prev값이 현재 node의 next 값이 된다.
      // 즉, 원래 node.next => 지워짐 / prev => 현재 node.next
    }
	return this;
}

...

SLL.reverse();
// {head: Node3, tail: Node1, length: 3}
// c -> b -> a



Tip. destructuring을 사용하면 변수 치환과 변수 할당을 좀 더 편리하게 한 줄로 처리할 수도 있다.

let [a, b] = [1, 2];
// a = 1, b= 2;

[a, b] = [b, a];
// a = 2, b = 1;


// 위의 코드에서 다음과 같이 처리할 수도 있었다.
[prev, node] = [node, next]; 

// 혹은 이렇게 할 수도 있었다.
[newNode.next, foundBeforeIndexNode.next] = [foundBeforeIndexNode.next, newNode]


단일 연결리스트의 Big O

삽입(insertion) : O(1)
데이터를 삽입하는데 탐색을 필요로 하지 않는다. (리스트의 중간의 경우 제외)

제거(removal) : O(1) or O(N)
데이터를 제거하는데 탐색을 필요로 하지 않는다. 다만 리스트의 끝에서 어떠한 값을 제거하기 위해서는 해당 node의 이전 node가 필요하기 때문에 탐색 과정이 필요하다.(리스트의 중간의 경우 제외)

탐색(searching) : O(N)
리스트를 탐색하기 위해서는 연결을 따라 순회하여야 하기 때문에 O(N)만큼 시간이 필요하게 된다.

접근(accessing) : O(N)
어떠한 값에 접근하기 위해서는 연결을 따라 순회하여야 하기 때문에 O(N)만큼 시간이 필요하게 된다.

profile
다음 포스트

[자료구조] 이중연결리스트 (Doubly Linked List)

4개의 댓글

comment-user-thumbnail
김일태
2023년 9월 10일

이거 면접에서 질문 받은 적 있는데 대답 못했던 기억이 있네요 ㅠ
항상 질문이 알고리즘과 그에 맞는 프론트 개발 경험을 연결지어서 물어보더라구요 !
같이 준비하시면 좋을 것 같습니다 ^.^

답글 달기
comment-user-thumbnail
윤뿔소
2023년 9월 10일

이런 형태도 자료구조로 쳤군요,, 저는 거의 처음 보는 거 같습니다! 잘 알고 갑니다 ㅎㅎ

답글 달기
comment-user-thumbnail
김소라
2023년 9월 10일

단일구조에 대해 자세히 알아갑니다 알고리즘은 저에겐 항상 어려운 존재였는데 정말 자세히 써주셔서 보기가 편했습니다!

답글 달기
comment-user-thumbnail
지은
2023년 9월 10일

리스트의 중간에 값을 추가하거나 삭제하려면 시간복잡도는 O(N)이 걸리는 걸까요? 😃

답글 달기