단일 연결 리스트

Doozuu·2023년 3월 7일

Big O GET INSERT Pop push remove reverse set shift unshift 단일 연결 리스트 자료구조

알고리즘&자료구조 (JS)

목록 보기

14/25

📌 단일 연결 리스트(Single Linked List)

연결 리스트 : 인덱스 없이 다수의 데이터(노드)들로 연결.

각각의 엘리먼트를 노드라고 한다.
각각의 노드는 문자열/숫자와 같은 하나의 데이터를 저장한다.
각 노드들은 다음 노드를 가리키는 정보 역시 저장해야 하며, 다음 노드가 없을 경우 null을 저장한다.
장점 : 삽입과 제거를 쉽게 할 수 있다.

세 가지 구성 요소

head : 연결 리스트의 시작 노드
tail : 연결 리스트의 마지막 노드
length : 전체 길이 추적

단일 연결 리스트 구현

class Node{
  constructor(val){
    	this.val = val;
    	this.next = null; // 다음 노드 정보
  }
}  

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

var list = new SinglyLinkedList()

단일 연결 리스트 메소드 구현

1. push( )

마지막에 새로운 노드 삽입

Push 메소드 만들기

Node를 새로 만들기
head가 없을 경우 head와 tail 설정
head가 있을 경우 tail 갱신
length 증가시키기
전체 리스트 반환

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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; // 리스트 전체 반환
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") // 메서드 사용
list.push("GoodBye")

2. pop( )

마지막 노드(tail)를 제거하고 새로운 tail 업데이트.

Tail을 제거하는건 간단하지만 새로운 테일을 업데이트 하는게 까다롭다. 리스트를 전부 순회해야 하기 때문이다.

두 개의 변수를 사용한다.

temp(current): 리스트의 끝까지 따라감.
pre(newTail): temp의 이전 값을 가리킴. 새로운 tail이 됨.

temp가 리스트의 끝을 가리킬 때 pre는 마지막에서 두 번째 노드를 가리킨다.

Pop 메소드 만들기

next가 있으면 계속 current와 newTail을 갱신한다.
next가 더이상 없으면(노드의 끝까지 도달하면) tail을 newTail로 갱신하고, 현재 태일을 null로 만든다. 길이도 감소시킨다.
길이가 0에 도달하면 head와 tail을 모두 null로 만든다.

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") // 메서드 사용
list.push("GoodBye")

3. shift( )

연결 리스트의 앞에서 노드를 제거한다.

헤드를 제거하고 그 다음 노드가 새로운 헤드가 되게 한다.

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
  shift(){
   		if(!this.head) return undefined;
    	var currentHead = this.head;
    	this.head = currentHead.next;
    	this.length--;
    	if(this.length === 0){
         	this.head = null;
          	this.tail = null;
        }
    	return currentHead;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") // 메서드 사용
list.push("GoodBye")
list.shift() // "Hello" 반환. list에는 GoodBye만 남아있음.

4. unshift( )

시작 지점에 새로운 노드를 추가하는 메소드

값을 받아서 새로운 노드를 만든다.
새로운 노드의 next가 현재 헤드값을 가리키게 한다.
새로운 노드를 헤드로 설정한다.
길이를 1 증가시킨다.

배열은 시작 지점에 새로운 노드를 추가하는 경우 배열 전체의 인덱스를 다시 수정해야 하지만, 단일 연결 리스트는 간단하게 추가할 수 있다.

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
  shift(){
   		if(!this.head) return undefined;
    	var currentHead = this.head;
    	this.head = currentHead.next;
    	this.length--;
    	if(this.length === 0){
         	this.head = null;
          	this.tail = null;
        }
    	return currentHead;
  }
  unshift(val){
    var 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;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") 
list.push("GoodBye")
list.unshift("First") // "First" "Hello" "GoodBye"

5. get( )

인덱스를 받아서 해당 위치에 있는 노드를 반환하는 메서드.

head부터 index만큼 순서대로 탐색해야 한다.
접근은 배열을 사용하는 것이 더 좋을 수 있다.

인덱스가 유효한지 체크(음수거나 전체 크기보다 큰지)
counter 변수와 current 변수를 만들고, next로 이동하면서 count 증가시키기(인덱스와 같아지기 전까지)
current 반환

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
  shift(){
   		if(!this.head) return undefined;
    	var currentHead = this.head;
    	this.head = currentHead.next;
    	this.length--;
    	if(this.length === 0){
         	this.head = null;
          	this.tail = null;
        }
    	return currentHead;
  }
  unshift(val){
    var 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;
  }
  get(index){
    if(index < 0 || index >= this.length) return null;
    var counter = 0;
    var current = this.head;
    while(counter !== index){
      	current = current.next;
     	counter++; 
    }
    return current;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") 
list.push("GoodBye")
list.get(1) // "GoodBye"

6. set( )

인덱스와 업데이트 할 값을 받아서 해당 위치의 값을 바꾸는 메소드
(해당 위치에 값이 이미 존재해야 한다.)

get 메소드를 활용한다.
T/F를 반환한다.

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
  shift(){
   		if(!this.head) return undefined;
    	var currentHead = this.head;
    	this.head = currentHead.next;
    	this.length--;
    	if(this.length === 0){
         	this.head = null;
          	this.tail = null;
        }
    	return currentHead;
  }
  unshift(val){
    var 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;
  }
  get(index){
    if(index < 0 || index >= this.length) return null;
    var counter = 0;
    var current = this.head;
    while(counter !== index){
      	current = current.next;
     	counter++; 
    }
    return current;
  }
  set(index, val){
    var foundNode = this.get(index);
    if(foundNode){
     	foundNode.val = val;
      	return true;
    }
    return false;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") 
list.push("GoodBye")
list.set(1,"two") // true
list // "Hello" "two"

7. insert( )

인덱스와 업데이트 할 값을 받아서 해당 위치에 값을 추가하는 메소드
(해당 위치에 값이 존재하지 않아도 된다.)

T/F를 반환한다.

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
  shift(){
   		if(!this.head) return undefined;
    	var currentHead = this.head;
    	this.head = currentHead.next;
    	this.length--;
    	if(this.length === 0){
         	this.head = null;
          	this.tail = null;
        }
    	return currentHead;
  }
  unshift(val){
    var 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;
  }
  get(index){
    if(index < 0 || index >= this.length) return null;
    var counter = 0;
    var current = this.head;
    while(counter !== index){
      	current = current.next;
     	counter++; 
    }
    return current;
  }
  set(index, val){
    var foundNode = this.get(index);
    if(foundNode){
     	foundNode.val = val;
      	return true;
    }
    return false;
  }
  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);
    // 값이 아닌 boolean을 반환하기 위해 !!을 붙여준다.(!은 Not을 의미하기 때문에 !!을 붙이면 true를 반환.)
    
    var newNode = new Node(val);
    var prev = this.get(index - 1);
    var temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") 
list.push("GoodBye")
list.insert(1,"insert") // true
list // "Hello" "insert" "GoodBye"

8. remove( )

인덱스를 받아서 해당 위치의 값을 제거하는 메소드

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
  shift(){
   		if(!this.head) return undefined;
    	var currentHead = this.head;
    	this.head = currentHead.next;
    	this.length--;
    	if(this.length === 0){
         	this.head = null;
          	this.tail = null;
        }
    	return currentHead;
  }
  unshift(val){
    var 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;
  }
  get(index){
    if(index < 0 || index >= this.length) return null;
    var counter = 0;
    var current = this.head;
    while(counter !== index){
      	current = current.next;
     	counter++; 
    }
    return current;
  }
  set(index, val){
    var foundNode = this.get(index);
    if(foundNode){
     	foundNode.val = val;
      	return true;
    }
    return false;
  }
  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);
    // 값이 아닌 boolean을 반환하기 위해 !!을 붙여준다.(!은 Not을 의미하기 때문에 !!을 붙이면 true를 반환.)
    
    var newNode = new Node(val);
    var prev = this.get(index - 1);
    var temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }
  remove(index){
   	if(index < 0 || index >= this.length) return undefined;
    if(index === 0) return this.shift();
    if(index === this.length - 1) return this.pop();
    
    var previousNode = this.get(index - 1);
    var removed = previousNode.next;
    previousNode.next = removed.next;
    this.length--;
    return removed;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") 
list.push("GoodBye")
list.remove(1) // "GoodBye"
list // "Hello"

9. reverse( )

리스트 전체의 순서를 바꾸는 메소드

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

class SinglyLinkedList{
  constructor(){
   		this.head = null; 
    	this.tail = null;
    	this.length = 0;
  }
  push(val){
    	var 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;
    	var current = this.head;
    	var 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;
  }
  shift(){
   		if(!this.head) return undefined;
    	var currentHead = this.head;
    	this.head = currentHead.next;
    	this.length--;
    	if(this.length === 0){
         	this.head = null;
          	this.tail = null;
        }
    	return currentHead;
  }
  unshift(val){
    var 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;
  }
  get(index){
    if(index < 0 || index >= this.length) return null;
    var counter = 0;
    var current = this.head;
    while(counter !== index){
      	current = current.next;
     	counter++; 
    }
    return current;
  }
  set(index, val){
    var foundNode = this.get(index);
    if(foundNode){
     	foundNode.val = val;
      	return true;
    }
    return false;
  }
  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);
    // 값이 아닌 boolean을 반환하기 위해 !!을 붙여준다.(!은 Not을 의미하기 때문에 !!을 붙이면 true를 반환.)
    
    var newNode = new Node(val);
    var prev = this.get(index - 1);
    var temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }
  remove(index){
   	if(index < 0 || index >= this.length) return undefined;
    if(index === 0) return this.shift();
    if(index === this.length - 1) return this.pop();
    
    var previousNode = this.get(index - 1);
    var removed = previousNode.next;
    previousNode.next = removed.next;
    this.length--;
    return removed;
  }
  reverse(){
   	var node = this.head;
    this.head = this.tail;
    this.tail = node;
    var next;
    var prev = null;
    for(var i=0; i<this.length;i++){
      	next = node.next;
      	node.next = prev;
      	prev = node;
      	node = next;
    }	
    return this;
  }
}  

var list = new SinglyLinkedList()
list.push("Hello") 
list.push("GoodBye")
list.reverse() // "GoodBye" "Hello"

📌 단일 연결 리스트의 Big O

삽입 : O(1)

삭제 : O(1) ~ O(n)

shift()할 때 O(1), pop()할 때 O(n)이다.
pop을 하려면 리스트를 전부 순회해야 하기 때문이다.

탐색 : O(n)

접근 : O(n)

삽입과 삭제의 경우 배열에 비해 우수하며, 탐색과 접근의 경우는 배열이 더 우수하다.

따라서 주어진 순서대로 데이터를 관리하고, 삽입과 삭제가 자주 일어나며, 탐색과 접근이 크게 필요하지 않은 경우에 단일 연결 리스트를 사용하는 것이 좋다.

Doozuu

모든게 새롭고 재밌는 프론트엔드 새싹

이전 포스트

자료구조

다음 포스트

단일 연결 리스트

알고리즘&자료구조 (JS)

📌 단일 연결 리스트(Single Linked List)

연결 리스트 : 인덱스 없이 다수의 데이터(노드)들로 연결.

세 가지 구성 요소

단일 연결 리스트 구현

단일 연결 리스트 메소드 구현

1. push( )

Push 메소드 만들기

2. pop( )

Pop 메소드 만들기

3. shift( )

4. unshift( )

5. get( )

6. set( )

7. insert( )

8. remove( )

9. reverse( )

📌 단일 연결 리스트의 Big O

삽입 : O(1)

삭제 : O(1) ~ O(n)

탐색 : O(n)

접근 : O(n)

자료구조

이중 연결 리스트

0개의 댓글