Linked list

haribo·2021년 4월 3일
0

CS

목록 보기
7/7

why?

배열과 자주 비교되는 Linked list

배열은 크기를 바꿀 수 없기 때문에 데이터 추가 삭제를 하려면 새로 배열을 만들어 주어야 하지만, Linked list는 크기 변동이 자유로워 데이터를 추가하고 삭제하기 용이하다.
다만, 조회에 있어선 배열이 더 빠르고 리스트 구조는 느리다는 단점이 있다.

Linked list?

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

상기 그림에 있는 구조를 보자.
새로 데이터를 추가할 때는 기존의 연결을 끊고, 새로 추가된 데이터의 주소 값에 포인터를 연결한다.
삭제 시엔 삭제할 노드의 주소값을 지우고, 삭제할 데이터 다음에 있는 노드의 주소로 포인터를 연결한다.

종류엔 단방향 연결리스트, 양방향 연결리스트가 있다.
끝에서부터 데이터를 조회할 땐 양방향 리스트가 빠르다.

code

LinkedList

package study.java.util;
public class LinkedList {
	Node header;
	
	static class Node {
		int data;
		Node next = null;
	}
	
	public LinkedList() {
		header = new Node();
	}
	
	public void append(int d) {
		Node end = new Node();
		end.data = d;
		Node n = header;
		while (n.next != null) {
			n = n.next;
		}
		n.next = end;
	}
	
	public void delete(int d) {
		Node n = header;
		while (n.next != null) {
			if (n.next.data == d) {
				n.next = n.next.next;
			} else {
				n = n.next;
			}
		}
	}
	
	public void retrieve() {
		Node n = header.next;
		while (n.next != null) {
			System.out.print(n.data + " -> ");
			n = n.next;
		}
		System.out.println(n.data);
	}
	
	public void removeDups() {
		Node n = header;
		while (n != null && n.next != null) {
			Node r = n;
			while (r.next != null) {
				if (n.data == r.next.data) {
					r.next = r.next.next;
				} else {
					r = r.next;
				}
			}
			n = n.next;
		}
	}
}

header를 쓰는 이유

기준점으로 쓸 노드가 삭제가 되어버리면, 다른 object에서 접근할때 데이터를 찾지 못할 수 있다. 따라서 데이터가 아닌, 관리용인 header 라는 노드를 별도로 생성하여 접근해준다.

참고

https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA/videos?view=0&sort=da

profile
그림 그리는 백엔드 개발자

0개의 댓글