연결리스트-JS

• 참고 사이트Linked-list1. 연결 리스트 ( Linked List )
• [Immersive_Sprint.js] LinkedList
• [자료구조] Linked List in JavaScript
•  

 

연결 리스트란?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조

단일 연결리스트

연결 리스트 종류

이 페이지에서는 단일 연결 리스트만 다루겠습니다 이중연결 리스트와 원형 리스트는 다음 페이지를 참고해주세요

1. 단일 연결 리스트

데이터 요소를 선형적으로 연결

• 기존 배열에 비해 링크 데이터 항목들을 메모리나 디스크에 연속적으로 할당할 필요가 없기 때문에 전체 구조를 재할당하거나 재구성하지 않고도 목록의 특정 지점에 요소를 추가 제거할때 유리
• 포인터로 다음 연결 리스트를 지정해야 되기 때문에 더 많은 메모리 사용
• 항목을 순차적으로 액세스 하지 않고 이전 리스트 값을 확인하기 위해서 전체 목록을 처음부터 다시 순서대로 읽어야함

2. 이중 연결 리스트

단일 연결 리스트와 다르게 한 노드에 두개의 링크가 존재

[JS]연결 리스트(Linked List) 개념 간단 정리

3. 원형 연결 리스트

마지막 노드가 처음 노드를 가리키는 연결 리스트

연결 리스트 특징

• 연속되는 항목들이 포인터로 연결된다
• 마지막 항목은 Null을 가리킨다
• 프로그램이 수행되는 동안 크기가 커지거나 작아질 수 있다
• (시스템 메모리가 허용하는 한) 힐요한 만큼 길어질 수 있다
• 메모리 공간을 낭비하지 않는다 (하지만 포인터를위한 추가의 메모리를 필요로 한다)

배열과 차이점

• 배열처럼 원소를 차례대로 저장하지만 원소들이 메모리 상에 연속적으로 위치하지 않는다
• 배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 속도가 떨어짐
• 즉, 탐색 또는 정렬을 자주 사용하면 배열을, 추가/삭제가 많으면 연결리스트를 사용하는게 좋다
• 배열은 push와 pop을 제외한 모든 배열의 요소 추가 및 제거 메서드에서 O(n)의 시간복잡도를 가짐. 첫번째 인덱스에 요소를 추가해야할 경우 나머지 모든 요소들을 오른쪽으로 한칸씩 옮겨야하기 때문⇒ 큐를 구현할 때 배열로 구현하는 것보다 연결리스트를 활용하는 것이 훨씬 효율적
• ⇒ 연결리스트는 필요한 만큼만 메모리가 늘어나고 줄어들며 첫번째 인덱스에 요소를 추가하더라도 O(1)의 시간 복잡도를 가짐, 단, 특정 위치의 데이터를 검색해내는 데에는 **O(n)**의 시간이 걸린다

구조

노드(Node)와 링크(Link)로 구성

노드

: 실제 정보를 담고 있는 하나의 단위

노드의 시작점은 head, 끝점은 tail이라고 부르면 노드의 추가, 삭제, 탐색가능

링크

: 노드 간의 위치 정보를 저장하고 있어 연결리스트 순서를 유지할 수 있도록 하는 연결고리

노드(Node)

연결 리스트에서 각 원소는 원소 자신과 다음 원소를 가리키는 포인터가 포함된 노드로 구성된다

노드

• 노드는 '데이터를 저장할 장소'와 '다른 변수를 가리키기 위한 장소'가 구분되어 있다
• 둘 이상의 Node가 연결된 상황

function Node(data) {
  this.data = data;
  this.next = null; 
}

연결리스트 ADT

ADT : 추상자료형(Abstract Data Type) 순수하게 기능이 무엇인지 나열한 것

addToTail(data)

: 리스트의 맨 끝에 데이터 추가

remove(위치)

: 해당 위치에 있는 데이터 삭제

indexOf(data)

: 해당 데이터의 인덱스를 반환한다. 존재하지 않을 경우 결과값은 -1

remove(data)

: 데이터를 삭제한다

insert(위치, 데이터)

: 해당위치에 데이터를 삽입한다

isEmpty()

: 데이터가 하나도 없다면 true를, 그 외엔 false를 반환

size()

: 데이터 개수를 반환한다. 배열의 length 프로퍼티와 비슷하다

---

수도코드 작성

• addToTail(value)
  1. head와 tail에 참조 연결
     • new를 이용해 node생성(let curNode = new Node())
  2. 만약 head가 비어있다면 ? 첫 연결이기 때문에 head와 tail에 node참조 연결을 해준다
  3. 만약 head가 비어있지 않다면?
     • tail.next에 node연결
     • tail에 node연결
• getNodeAt(index)
  1. 헤드를 변수에 저장한다
  2. 만약 index가 size보다 크다면?
     • undefined에 저장한다
  3. 만약 index가 size보다 작다면?
     • for문을 돌리는데 i<index로 설정
     • 1번 변수를 1번의 변수.next로 설정해서 index까지 도달
     • 그 index를 리턴
• contains(value) - 해당 값 연결 리스트 있는지 판별
  1. 헤드를 curNode 변수에 저장한다
  2. while문을 설정함. curNode가 있을 때까지
  3. 해당 인덱스와 curNode.value가 같다면 리턴 true
     • 같지 않다면 curNode = curNode.next
• idnexOf(value) - 해당 값 어떤 인덱스에 있는지 반환
  1. 헤드를 curNode변수에 저장
  2. indexCount변수를 설정
  3. while문을 설정함. curNode있을 때까지
  4. 해당 인덱스와 curNode.value가 같다면 인덱스 변수 리턴
  5. 아니면 인덱스 변수++, curNode = curNode.next
• remove(value) - 해당하는 연결 리스트의 값을 지웁니다
  1. 만약 헤드가 없다면 undefined리턴
     • 만약 헤드 value와 value가 같다?
     • head를 prevNode로 설정
     • 현재 오브젝트 리턴
  2. head를 prevNode로 설정(그러니까 0번째)
  3. head.next를 curNode로 설정 (그러니까 1번째)
  4. 만약 curNode.value가 value와 값이 같다? break
  5. 만약 값이 같지 않다?
     • prevNode = curNode
     • curNode = curNode.next (한칸씩 당겨줌)
  6. curNode.value값이 같을 때 다음 노드값으로 초기화
  7. size--
  8. 오브젝트 리턴

---

JS 구현

노드와 연결 리스트 구현

class Node {
	constructor(data) {
		this.data=data;
		this.next=null; //다음 노드를 저장하는 변수
	}
}
class LinkedList{
	constructor() {
		this.length=0;//리스트 노드 개수
		this.head=null;
		this.tail=null;
	}
}

LinkedList클래스 안에 메소드구현

1. addToTail(value) - 주어진 값을 연결리스트 끝에 추가

addToTail(data) {
	let addData = new Node(data);
	if (this.head === null && this.tail === null) {
		this.head = addData;
		this.tail = addData;
	}
	if (this.head !== null) {
		this.tail.next = addData;
		this.tail = addData;
	}
	this.length++;
}

출력

const Linked = new LinkedList();
console.log(Linked)
Linked.addToTail('google')
Linked.addToTail('apple')
Linked.addToTail('samsung')
Linked.addToTail('yellow')
Linked.addToTail('yanolza')
Linked.addToTail('tesla')

LinkedList {
  length: 6,
  head: Node { data: 'google', next: Node { data: 'apple', next: [Node] } },
  tail: Node { data: 'tesla', next: null }
}

2. remove(data) - 주어진 값을 찾아서 연결을 해제

remove(data) {
	//데이터가 비어있으면 undefined 반환
	if (this.head === null) {
		return undefined;
	}
	//리스트 처음 값이 찾는 값과 같다면
	if (this.head.value === value) {
		//this.head를 다음 노드로 지정하여 아무도 가리키지 않게 만들어 가비지콜렉터에 추가
		this.head = this.head.next;
		this.length--;
	}
	let preNode = this.head;
	let curNode = this.head.next;
	//리스트 중간에 찾는 값이 존재하는지 확인
	//찾는 값이 리스트에 없으면 curNode가 tail.next가 되면 null이므로 루프 종료됨
	while (curNode) {
		//curNode.value값이 같으면
		if (curNode.data === data ) {
			preNode.next = curNode.next;
			this.length--;
			break
		}
		else {
			//찾는 값이 나올 때까지 다음 노드로 초기화
			preNode = curNode;
			curNode = curNode.next;
		}
	}

}

출력값

Linked.remove('yellow')
Linked.remove('apple')
console.log(Linked)

LinkedList {
  length: 4,
  head: Node { data: 'google', next: Node { data: 'samsung', next: [Node] } },
  tail: Node { data: 'tesla', next: null }
}

3. getNodeAt(index) - 주어진 인덱스 노드를 찾아서 반환. 해당 인덱스에 노드 없으면 undefined반환

getNodeAt(index) {
	//리스트의 처음부터 탐색
	let headNode = this.head;
	//인덱스 넘버가 리스트의 크기를 초과한다면 undefined
	if (index > this.length) {
		return undefined
	} else {
		//인덱스 넘버에 도달할 때까지 루프함
		for (let i = 0; i < index; i++) {
			//다음 노드로 계속 초기화
			headNode = headNode.next
		}
		return headNode;
	}

}

출력값

console.log(Linked.getNodeAt(5))
console.log(Linked.getNodeAt(1))

undefined
Node {
  data: 'samsung',
  next: Node { data: 'yanolza', next: Node { data: 'tesla', next: null } }
}

4. contains(data) - 연결 리스트에 주어진 값을 가지는 노드의 존재 여부 반환

contains(data) {
	//리스트 처음부터 탐색함	
	let curNode = this.head;
	//리스트에 값이 존재하지 않는다면 ourNode는 null이 되므로 while루프는 종료되고 false가 리턴됨
	while (curNode) {
		if (curNode.data === data) {
			return true
		}
		else {
			//값을 찾을 때까지 다음 노드로 초기화
			curNode = curNode.next
		}
	}
	return false
}

출력값

console.log(Linked.contains('samsung'))

true

5. indexOf(data) - data의 index반환

indexOf(data) {
	let curNode = this.head;
	let indexCount = 0;
	while(curNode) {
		if (curNode.data===data) {
			return indexCount;
		}
		else {
			indexCount ++;
			curNode = curNode.next;
		}
	}
	return -1
}

출력값

indexOf('google')

0

6. size() - 연결리스트 크기 반환

size() {
	return this.length
}

출력값

console.log(Linked.size())

4

전체코드

class Node {
	constructor(data) {
		this.data=data;
		this.next=null; //다음 노드를 저장하는 변수
	}
}
class LinkedList{
	constructor() {
		this.length=0;//리스트 노드 개수
		this.head=null;
		this.tail=null;
    }
    addToTail(data) {
        let addData = new Node(data);
        if (this.head === null && this.tail === null) {
            this.head = addData;
            this.tail = addData;
        }
        if (this.head !== null) {
            //이때 tail은 그 전 맨끝 값 
            this.tail.next = addData;
            //여기서 tail은 새로 추가되는 맨 끝값
            this.tail = addData;
        }
        
        this.length++;
    };
    remove(data) {
        //데이터가 비어있으면 undefined 반환
        if (this.head === null) {
            return undefined;
        }
        //리스트 처음 값이 찾는 값과 같다면
        if (this.head.data === data) {
            //this.head를 다음 노드로 지정하여 아무도 가리키지 않게 만들어 가비지콜렉터에 추가
            this.head = this.head.next;
            this.length--;
        }
        let preNode = this.head;
        let curNode = this.head.next;
        console.log('pre,cur', preNode, curNode)
        //리스트 중간에 찾는 값이 존재하는지 확인
        //찾는 값이 리스트에 없으면 curNode가 tail.next가 되면 null이므로 루프 종료됨
        while (curNode) {
            if (curNode.data === data) {
                preNode.next = curNode.next;
                this.length--;
                break
            }
            else {
                //찾는 값이 나올 때까지 다음 노드로 초기화
                preNode = curNode;
                curNode = curNode.next;
            }
        }
    }
    
    getNodeAt(index) {
        //리스트의 처음부터 탐색
        let headNode = this.head;
        //인덱스 넘버가 리스트의 크기를 초과한다면 undefined
        if (index > this.length) {
            return undefined
        } else {
            //인덱스 넘버에 도달할 때까지 루프함
            for (let i = 0; i < index; i++) {
                //다음 노드로 계속 초기화
                headNode = headNode.next
            }
            return headNode;
        }
    }
    contains(data) {
        //리스트 처음부터 탐색함	
        let curNode = this.head;
        //리스트에 값이 존재하지 않는다면 ourNode는 null이 되므로 while루프는 종료되고 false가 리턴됨
        while (curNode) {
            if (curNode.data === data) {
                return true
            }
            else {
                //값을 찾을 때까지 다음 노드로 초기화
                curNode = curNode.next
            }
        }
        return false
    }
    indexOf(data) {
        let curNode = this.head;
        console.log(curNode)
        let indexCount = 0;
        while(curNode) {
            if (curNode.data === data) {
                return indexCount;
            }
            else {
                indexCount ++;
                curNode = curNode.next;
            }
        }
        return -1
    }

    size() {
        return this.length
    }
}
const Linked = new LinkedList();
// console.log(Linked)
Linked.addToTail('google')
// console.log(Linked)
console.log(Linked.tail.next)
Linked.addToTail('apple')
// console.log(Linked)
console.log(Linked.tail.next)
Linked.addToTail('samsung')
// console.log(Linked)
Linked.addToTail('yellow')
Linked.addToTail('yanolza')
Linked.addToTail('tesla')
// console.log(Linked)
Linked.remove('yellow')
Linked.remove('apple')
console.log(Linked)
console.log(Linked.getNodeAt(5))
console.log(Linked.getNodeAt(1))
console.log(Linked.contains('samsung'))
console.log(Linked.indexOf('samsung'))
console.log(Linked.size())