LinkedList 개념, 사용법, 코드

 

LinkedList 의 개념

---

https://opentutorials.org/module/1335/8821

ArrayList

• 배열의 구조를 사용한다.
  • 그렇기 때문에 데이터를 삭제하거나 추가하면 더 큰 공간으로 (또는 더 작은 공간으로) 이동해야 한다. (시간이 많이 소요됨)
  • 만약 크기가 5인 list에 중간에 데이터를 추가하면 그 다음에 있는 데이터들을 한칸 씩 모두 이동시켜야 하므로 (만약 크기가 1억이면? 엄청나다.)
• 원하는 인덱스에 바로 접근이 가능하다.

 

LinkedList

• 연결(link)된 구조이다.
• ArrayList와 가장 큰 차이점이 데이터들이 여기저기 흩어져 있다.
  • 장점 :
    • 데이터를 추가하거나 삭제할 때, 이전 값과 추가(또는 삭제)할 값의 next만 변경하면 되므로 훨씬 빠르다.
  • 단점 :
    • 원하는 인덱스에 직접 접근이 안된다.
    • 노드에는 [데이터 + 다음 노드] 가 들어있기 때문에 head에서 부터 다음 노드를 찾고 찾아서 해당 인덱스까지 이동해서 찾아야하므로 ArrayList에 비해 훨씬 느리다.

 

 

LinkedList의 구조

---

arrayList는 엘리먼트라고 불렀지만, LinkedList에서는 노드(node) 라고 부른다. 다른 용어로는 정점(vertex)이 있다.

https://opentutorials.org/module/1335/8821

노드는 두가지 정보를 가지고 있어야 한다.

1. 노드의 값
2. 다음 노드

 

 

노드를 처음위치에 추가

---

https://visualgo.net/en/list
위 사이트에 가면, 리스트와 트리 등등 다른 구조의 대한 이해를 그림으로 잘 설명해 놓은 사이트 이다. 참고하면 좋을 것 같다.

https://visualgo.net/en/list

삽입하려는 노드를 head를 가리키게 한 다음,

Vertex newNode = new Vertex(85); // 85 생성
newNode.next = head; // 85의 next를 현재 head로 설정한다.
head = newNode; // 그리고 85를 head로 설정한다.

https://visualgo.net/en/list

원래 head 였던 노드를 삽입하려는 노드로 바꾼다.

 

노드를 중간위치에 추가

---

https://visualgo.net/en/list

새로운 노드 90을 index=2인 23의 자리에 추가하고 싶다. 어떻게 해야 할까?

• 먼저 6과 23을 찾는다.
  • 6의 next를 90으로
  • 90의 next를 23으로 설정

Vertex newNode = new Vertex(90); // 새로운 노드

//  6 (23의 이전 노드)의 위치를 먼저 찾는다. index = 2;
Vertex previous = head;

for(int i=0; i<1; i++) {
	previous  = previous.next;
}

//---------------------------------------------------

Vertex present = previous.next; // 현재 값에 6.next = 23을 저장

previous.next = newNode; // 6의 next를 새로운 노드(90) 으로 설정
newNode.next = present; // 새로운 노드(90)의 next를 23으로 설정

 

https://visualgo.net/en/list

 

 

노드를 마지막에 추가

---

https://visualgo.net/en/list

마지막에 80이라는 노드를 추가한다고 가정해보자.

바로 tail로 접근해서 tail.next를 80으로 지정해주면 끝이다!

반드시 tail을 변경해주어야 한다!!

Vertex newNode = new Vertex(80); // 80을 새로 생성하고

tail.next = newNode; // tail.next를 80으로 지정한 뒤

tail = newNode; // 다시 tail을 80으로 변경해준다.

 

 

데이터로 노드의 인덱스 조회

https://visualgo.net/en/list

우리가 6을 찾고자 한다면 head부터 검사를 하면서 6인지 확인 후 6이 맞다면 증가 시켰던 index를 반환하고, 만약 cur.next가 null이면 NOT FOUND를 리턴한다. 

// findNum = 6;
int index = 0;

Vertex cur = head;

while(cur != findNum) { // cur이 6인가?
	cur = cur.next; // 아니면 cur.next
    index++; // 인덱스 증가
    
    if(cur == null){
    	System.out.println("NOT FOUND");
        return ;
    }
}

System.out.println(findNum + "의 인덱스는 : " + index); // findNum의 인덱스는 : 3
return ;

 

인덱스로 데이터 조회

https://visualgo.net/en/list

만약에 인덱스로 3을 받았다고 하면, 해당하는 수가 6일 것이다. 

메소드 내부에 count 변수를 만들어서 하나씩 증가시키면서 index와 같아지는 시점에 해당 값을 반환하면 된다.

// index = 3;(4번째 수)

int count = 0;
Vertex find = head;

while(count++ != index) { // count를 증가시키면서 index와 같아지는 시점에 종료한다.
	find = find.next; // 계속 다음 노드의 데이터로 바꿔준다.
    if(find == null) {
    	System.out.println("NOT FOUND");
        return ;
    }
}

System.out.println(index + "에 해당하는 수는 : " + find); // 이 시점에 count는 4(++로 인해)가 되어있어서 index를 출력시킨다.
return ;

 

 

데이터 삭제

https://visualgo.net/en/list

인덱스가 3인 데이터를 삭제한다고 가정해보자.

while문으로 일단 인덱스가 2인 노드를 찾고, next를 삭제할 노드의 다음 데이터를 넣어주면 된다!

// index : 3

Vertex pre = head;

while(--index != 0) {
	pre = pre.next;
}

Vertex delNode = pre.next; // 삭제 할 노드 : 6

// next를 바꿔주기
pre.next = delNode.next;

Delete delNode; // 해당 노드 삭제

 

 

References

---

visualgo.net/en/list

VisuAlgo - Linked List (Single, Doubly), Stack, Queue, Deque

opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)