TIL 정리_46(Linked List)

유튜브 엔지니어 대한민국 강의를 듣고 정리한 내용입니다

https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA

 

 

Linked List 개념

컴퓨터에 자료를 저장하는 구조의 한 종류

일렬로 연결된 데이터를 저장할 때 사용한다

데이터 추가 및 삭제에 용이

데이터 조회는 ArrayList가 사용하기 좋다

배열과의 비교 : 배열은 방들이 물리적으로 한 곳에 모여있어 늘이거나 줄일 수 없다

링크드 리스트는 중간에 추가하고 싶은 경우 해당 노드의 주소를 변경하여

추가가 가능하다 삭제도 동일한 방식으로 가능하다

 

 

노드(포인터)를 삭제할 경우

노드가 링크드 리스트에서 삭제되었지만 메모리가 남아있다

-> 자바는 가비지 컬렉터가 알아서 삭제하지만 C나 C++는 삭제코드를 써야 한다

길이가 정해지지 않는 데이터를 다룰때에는 링크드 리스트가 좋다

 

 

단방향 양방향 LinkedList 개념

길이가 정해져 있지않은 데이터의 집합

데이터를 저장한 노드에 다음 노드의 주소를 가지고 있는 형태이다

 

단방향 링크드 리스트 : 한 개씩 노드를 검색해가면서 한 방향으로만 검색 가능하다

양방향 링크드 리스트 : 주소를 가지고 있고 추가로 앞에 있는 노드의 주소를 가지고 있다

 

양방향 링크드 리스트에서의 데이터 삽입

노드를 하나 생성하고 삽입하고자 하는 전 노드가 가지고 있던 다음 주소를 본인이 갖는다

양쪽 끝에 포인터를 저장하고 있다 하지만 메모리를 많이 차지하기 때문에 필요에 따라 사용유무를 정해야 한다

 

 

단방향 링크드 리스트 자바로 구현

class Node {
int data;
Node next = null;
Node(ind d) {
this.data = d
}

 

클래스안에 데이터 추가

(원래는 boolean 타입을 리턴해야 한다)

void append(int d) {
Node end = new Node(d); //새로운 노드를()안의 값으로 만들어라
Node n = this;
while (n.next != null) {
n = n.next;
}
n.next = end;
}

 

데이터 삭제

void delete(int d) {
Node n = this; //임의의 포인터
while(n.next != null) { //노드를 돌면서 마지막 노드가 아닐때까지
if(n.next.data = d) {
}
n.next = n.next.next; //다음 노드는 사라진다
} else {
n = n.next; //delete
}
}

 

 

현재 링크드 리스트에 무엇이 있는지 나열

void retrieve() {
Node n = this;
while(n.next != null) {
System.out.print(n.data +“->”);
n = n.next; //다음 노드로 이동하면서 출력
}
System.out.println(n.data) //처음부터 끝까지 노드 출력
}

public class SinglyLinkedList { //단방향 링크드 리스트
public static void main (String args[]) {
Node head = new Node(1);
head.append(2);
head.append(3);
head.append(4);
head.retrieve();
head.delete(2);
head.delete(3);
head.retrieve();
}
 

 

 

LinkedListNode 노드 클래스를 감싸는 링크드 리스트

단방향 링크드 리스트의 첫 번째 노드는 삭제하면 문제가 생긴다

-> 노드 클래스를 링크드 리스트 클래스에 감싸준다

 
class LinkedList {
Node header;

static class Node {
int data;
Node next = null;
}
LinkedList() {
header = new Node();
}
 
}