Linked List

louis220·2021년 1월 26일
0

Linked List

Linked List는 노드들의 모임이다

각 노드는 값이 들어가는 Data Field와 다음노드의 위치가 담겨 있는 Link Field로 이루어져 있다
보통 Data Field에는 value라는 이름의 변수, link Field에는 next변수를 사용한다
value에는 노드의 값( 12 , 06, 71 등)이 저장되고 next에는 다음 노드의 포인터나 참조값을 저장해서 노드와 노드를 열결시키는 방법을 사용한다
또한 head 와 tail을 지정해 첫노드와 끝노드를 지정합니다.

노드의 추가

노드를 맨 첫 번째 위치나 끝 위치에 추가하기 위해서는 노드를 연결해줌 + head나 tail을 추가한 노드의 값으로 변경하는 작업도 잊지 않아야 한다

20이라는 값을 첫위치에 추가해보자
1 새로운 노드를 생성한다

    let temp = new LinkedList(20)
    

2 새로운 노드의 다음 노드로 head를 가리켜준다

	temp.next = head //현재 head가 가리키고 있는 Node 즉 12를 말한다

3 새로 추가된 노드가 head가 될 수 있도록 head의 값을 변경

	head = temp

노드를 중간에서 추가해보자
추가하기 위해서는 추가할 위치의 전노드와 후노드와의 link연결이 추가로 필요하다
06과 71 사이에 20이라는 값을 가진 노드를 넣기 위해서는 06의 다음 노드가 20이며 20 다음노드가 71이라고 설정을 해주어야 한다.

=> 코드추가

노드의 제거

다른 data(array나 object)같이 데이터를 제거한다 라는 식으로 제거되지 않는다
노드의 연결을 끊은 뒤 삭제를 해야 완전히 제거가 된다
제거하려는 노드의 전노드의 next를 제거하려는 노드의 후노드와 연결하면 제거하려는 노드는 연결이 끊기게 되고 그 후에 메모리에서 제거해준다

=> 코드추가

Array List와 비교해보자면 인덱스 조회는 array가 추가/ 삭제는 Linked List가 빠르다

profile
기록을 하자

0개의 댓글