[Data Structure] Java 링크드 리스트(LinkedList) 구현

• 이 글은 "온라인 자바 스터디 내용"을 정리한 글입니다.

LinkedList란?

• 링크드 리스트를 노드와 노드를 연결하여 데이터를 담는 방식인 자료구조입니다.
• 링크드 리스트의 멤버변수로 데이터와 포인터가 존재하여 포인터로 다음 노드를 가리키는 방식입니다.
• 링크드 리스트와 배열과의 차이점은 명백히 존재합니다. 배열은 한 줄로 나열된 메모리 공간에 데이터를 담는 자료구조로 인덱스로 데이터에 접근 할 수 있습니다.
• 하지만 배열은 추가, 삭제가 용이하지 않습니다. 반면, 링크드 리스트는 메모리 공간과 상관없이 하나의 노드끼리 연결하다 보니 메모리 사용 측면에서 효율적입니다. 추가, 삭제도 용이하지만 인덱스가 없어 탐색하기에는 적합하지 않습니다.

LinkedList 구현

자바에서 인스턴스 전달은 레퍼런스입니다

• 참조(https://shyunku.tistory.com/38)

public class ListNode {
    int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
        next = null;
    }
}

먼저 ListNode를 구현하여 data와 다음 노드를 가리키는 next를 가지도록 클래스를 작성합니다.
다음 노드로 연결하여 하나의 연결리스트가 생성하는 것입니다.

	public class LinkedList {
	int size;
	public LinkedList() {
	size = 0;
	}
	public int getSize() {
	return size;
	}
	ListNode add(ListNode head, ListNode nodeToAdd, int position) {
	ListNode node = head;
	if(size<position){
	return null;
	}
	if (head == null) {
	node = nodeToAdd;
	head = node;
	} else {
	for (int i = 1; i < position; i++) {
	node = node.next;
	}
	nodeToAdd.next = node.next;
	node.next = nodeToAdd;
	}
	size++;
	return head;
	}
	ListNode remove(ListNode head,int positionToRemove){
	ListNode node = head;
	if(size<=positionToRemove || head == null){
	return null;
	}
	if(positionToRemove == 0){
	node = node.next;
	head = node;
	} else{
	for(int i=1;i<positionToRemove;i++){
	node = node.next;
	}
	node.next = node.next.next;
	}
	size--;
	return head;
	}
	boolean contains(ListNode head, ListNode nodeTocheck){
	ListNode node = head;
	boolean check = false;
	if(head == null){
	return false;
	}
	do{
	if(node.data == nodeTocheck.data && node.next == nodeTocheck.next){
	check = true;
	break;
	}
	node = node.next;
	}while(node!=null);
	return check;
	}
	}

view raw LinkedList.java hosted with ❤ by GitHub

• ListNode add(ListNode head, ListNode nodeToAdd, int position) : head는 링크드 리스트의 맨 앞 노드를 가리키며 nodeToAdd 노드를 해당 position에 추가하는 함수
• ListNode remove(ListNode head, int positionToRemove) : 링크드 리스트에서 positionToRemove에 해당하는 위치의 데이터를 삭제하는 함수
• boolean contains(ListNode head, ListNode nodeTocheck) : 링크드 리스트에서 nodeTocheck 노드가 있는지 확인하는 함수