1. Linked List란?
**연결 리스트(Linked List)**는 데이터를 저장하는 노드(Node)들이 연결된 자료구조
각 노드는 값(value)과 다음 노드를 가리키는 포인터(next)를 가짐
✔ 배열(Array)와의 차이점
배열 (Array)연결 리스트 (Linked List)
| 저장 방식 |
연속된 메모리 공간 |
노드가 메모리 여기저기 흩어져 있음 |
| 삽입/삭제 속도 |
느림 (중간 삽입 시 데이터 밀어야 함) |
빠름 (포인터만 변경) |
| 검색 속도 |
빠름 (index로 접근 가능) |
느림 (first부터 순차 탐색) |
package linkedlist;
public class App {
public static void main(String[] args) {
// Node n1 = new Node();
// n1.value="한조";
// Node n2 = new Node();
// n2.value="티모";
// n1.next=n2; //링크연결! 노드의 핵심
//실질적인 코드
LinkedList<String> list = new LinkedList<>();
list.add("한조");
list.add("티모");
list.add("메르시");
list.add("베인");
list.add("아호");
String r1 = list.get(2);
System.out.println(r1);
list.add(2,"솜브라");
String r2 = list.get(4);
System.out.println(r2);
list.remove(0);
list.remove(0);
String r3 = list.get(0);
System.out.println(r3);
}
}
//알고리즘 linkedlis
//노드에는 value가 포함되어있음
//linked는 따라가는게 핵심
//핵심 코어 구조
class Node<E>{ //node를 선언할때 E면 E를 선언?? generic
E value; // 값 (데이터)
Node<E> prev; //양방향으로 움직일 수 있음
Node<E> next; // 다음 노드를 가리키는 포인터
}
//API
class LinkedList<E>{
private Node<E> first = null; //한번도 add가 되지 않았다는 것을 의미
// 첫 번째 노드를 가리키는 변수 (처음에는 null)
public void add(E value){
Node<E> newNode = new Node<>(); // 새로운 노드 생성
newNode.value=value; // 값 저장
//힙메모리에 올라감 -> 참조변수에 머시기?
if (first==null) {
first = newNode; // 리스트가 비어있으면 첫 번째 노드로 설정
//newNode연결
return; //왜 리턴??? 이해가 아리마셍이여어어엉
//만약 리스트가 비어있다면 첫번째 노드로 설정한 후 return으로 빠져나옴
//return이 없으면 while문이 실행되는데 first노드만 있을때 무한반복됨
}
Node<E> temp = first; // 첫 번째 노드부터 시작
while(true){
if(temp.next ==null){
break; // 마지막 노드 찾기
}
temp = temp.next; // 다음 노드로 이동
}
temp.next = newNode; // 마지막 노드의 next에 새 노드 연결
}
//링크드 리스트의 장점
public void remove(int index){
if(index==0){
first=first.next;
return;
}
Node<E> temp = first;
for(int i=0; i<index-1; i++){ //앞에걸 찾아야해서 -1
temp=temp.next; //따라간다는 말 중요 코드 !!
}
temp.next=temp.next.next; //티모를 지우려하고있음
}
//중간에 값 추가(삽입)
//오버로딩
public void add(int index, E value){
Node<E> newNode = new Node<>();
newNode.value=value;
Node<E> temp = first;
for(int i =0; i<index-1; i++){
temp=temp.next;
}
newNode.next=temp.next;
temp.next=newNode;
}
//연결만 잘하면됨
//접근 - 최대 약점
public E get(int index){
Node<E> temp = first;
for(int i=0; i<index; i++){
temp = temp.next;
}
return temp.value;
}
}
2. 기본 구조
[한조] → [티모] → [메르시] → null
- 첫 번째 노드: first가 가리킴
- 마지막 노드의 next는 null (연결 종료)
📌 코드 구조
class Node<E> {
E value; // 데이터 값
Node<E> next; // 다음 노드 가리키는 포인터
}
3. 중간 삽입
📌 예제: "겐지"를 "한조"와 "티모" 사이에 추가
first → [한조] → [겐지] → [티모] → [메르시] → null
public void add(int index, E value){
Node<E> newNode = new Node<>();
newNode.value = value;
Node<E> temp = first;
for(int i = 0; i < index - 1; i++){
temp = temp.next; // 삽입할 위치 찾기
}
newNode.next = temp.next; // 새 노드가 다음 노드를 가리키게 함
temp.next = newNode; // 이전 노드의 next를 새 노드로 변경
}
📌 while 문이 꼭 필요한 이유
✔ 첫 번째 노드(= first)는 바로 추가할 수 있지만, 이후 추가되는 노드는 마지막 노드에 연결해야 하기 때문!
✔ 마지막 노드를 찾으려면 리스트를 처음부터 끝까지 탐색해야 함
✔ 즉, while 문이 없으면 마지막 노드를 찾을 수 없어서 연결이 안 됨
📌 while 문이 없는 경우 → 문제 발생!
while 문을 없애고 다음과 같이 작성하면 어떻게 될까?
first → [한조] → [메르시] ❌ (티모가 사라짐!)
- "한조" 다음 노드가 "메르시"가 되어버림!
- 중간에 "티모"가 사라지는 문제 발생
- "한조"의 next를 "티모"가 아니라 "메르시"로 덮어쓰기 때문
▶제네릭(Generic) 사용
코드에서 Node<E>처럼 <E>가 붙어 있는 게 보이나?
이건 제네릭(Generic) 문법을 사용한 거야.
제네릭을 사용하면, 어떤 데이터 타입이든 유연하게 저장할 수 있음!
예시
- Node<Integer> → 정수를 저장하는 노드
- Node<String> → 문자열을 저장하는 노드
- Node<Double> → 실수를 저장하는 노드
▶null로 끝나는 이유
① 마지막 노드를 구분하기 위해
연결 리스트에서 마지막 노드를 찾으려면, 어디까지가 리스트의 끝인지 알아야 함
만약 next가 null이면 이 노드가 마지막 노드라는 걸 쉽게 알 수 있ㅇ,ㅁ!
② 새로운 노드를 추가할 때 필요
③ 순환 참조(무한 루프)를 방지하기 위해
만약 마지막 노드의 next가 null이 아니라 자기 자신을 가리킨다면?
[한조] → [티모] → [메르시] → (자기 자신) 🔄 무한 반복!
- 이렇게 되면 무한 루프가 발생해서 프로그램이 멈추지 않게 됨
- 그래서 연결 리스트는 마지막을 null로 끝내야 안전함
▶언제 연결 리스트를 사용할까?
✅ 데이터 크기를 미리 모를 때 → 배열은 크기가 고정되지만, 연결 리스트는 동적으로 확장됨
✅ 데이터 삽입/삭제가 많을 때 → 배열은 이동이 필요하지만, 연결 리스트는 포인터만 수정하면 됨
✅ 메모리를 효율적으로 사용해야 할 때 → 필요할 때마다 노드를 생성할 수 있음