๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
IT

[์ž๋ฃŒ๊ตฌ์กฐ] Linked List

by yunamom 2022. 5. 23.
๋ฐ˜์‘ํ˜•

์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Linked List)

์—ฐ๊ฒฐ๋  ๋‹ค์Œ ์šด์†Œ์— ๋Œ€ํ•œ ์ฃผ์†Œ๋ฅผ ์ €์žฅํ•ด์•ผ ํ•˜๋ฏ€๋กœ <data + link> ์˜ ๋‹จ์œ„๋กœ ์ €์žฅํ•œ๋‹ค.(์ด์™€ ๊ฐ™์€ ๋‹จ์œ„๋ฅผ Node ๋ผ๊ณ  ํ•จ)

์ฆ‰, ์‹œ์ž‘(์ฃผ์†Œ) - ์—ฐ๊ฒฐ(Link) - ๋(Null Pointer or Circular) ์™€ ๊ฐ™์€ ์ˆœ์„œ๊ฐ€ ์กด์žฌ

 

1. ๋‹จ์ˆœ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Singly Linked List)

Singly Linked List (๋‹จ์ผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ)

2. ์›ํ˜• ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Circular Linked List)

Circular Linked List (์›ํ˜• ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ)

3. ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (Doubly Linked List)

Doubly Linked List (์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ)

 

 Linked List ์˜ˆ์ œ 

package linkedList;

public interface LinkedList {
    ListNode add(ListNode head, ListNode nodeToAdd, int position);
    ListNode remove(ListNode head, int positionToRemove);
    void printList(ListNode head);
    boolean contains(ListNode head, ListNode nodeToCheck);
}
package linkedList;

public class ListNode implements LinkedList{
    int data;
    private ListNode next;

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

    public ListNode() {

    }

    @Override
    public ListNode add(ListNode head, ListNode nodeToAdd, int position) {
        // ์ดˆ๊ธฐ ์ƒํƒœ
        if (position == 0 && head == null) {
            head = nodeToAdd;
            return head;
        }
        // ๋งจ ์•ž์— add
        else if (position == 0){
            nodeToAdd.next = head;
            head = nodeToAdd;

            return head;
        }

        ListNode node = head;
        // find pos
        for (int i = 0; i < position - 1; i++) {
            node = node.next;
        }
        // ํ•ด๋‹น pos์— add
        nodeToAdd.next = node.next;
        node.next = nodeToAdd;
        return head;
    }
    @Override
    public ListNode remove(ListNode head, int positionToRemove) {
        if (positionToRemove == 0) {
            head = head.next;
            return head;
        }
        else {
            ListNode node = head;
            for(int i=0; i< positionToRemove; i++) {
                node = node.next;
            }
            node.next = node.next.next;
            return head;
        }
    }

    @Override
    public void printList(ListNode head) {
        ListNode node = head;
        while (node != null) {
            System.out.print(node.data);
            node = node.next;
        }
        System.out.println();
    }

    @Override
    public boolean contains(ListNode head, ListNode nodeToCheck) {
        ListNode node = head;
        while(node != null) {
            if (node.data == nodeToCheck.data) {
                return true;
            }
            node = node.next;
        }
        return false;
    }
    public static void main(String[] args)  {
        LinkedList nums = new ListNode();

        ListNode head = null;
        for(int i=0; i<5; i++) {
            head = nums.add(head, new ListNode(i), i);
        }
        nums.printList(head);
        head = nums.remove(head, 0);
        head = nums.remove(head, 0);
        nums.printList(head);
        System.out.println(nums.contains(head, new ListNode(3)));
        System.out.println(nums.contains(head, new ListNode(1)));
    }
}
package linkedList;


public class ListNodeStack {
	
	private ListNode head;
	private int top;
	
	public ListNodeStack() {
		this.head = new ListNode();
		this.top = -1;
	}
	public void push(int data) {
		ListNode listNode = new ListNode(data);
		head.add(this.head, listNode, ++top);
	}
	public int pop() {
		if(top == -1) {
			System.out.println("Empty");
			return top;
		}
		return head.remove(head,--top).data;
	}
	public void print() {
		head.printList(head);
	}
	public static void main(String[] args) {
		ListNodeStack listNodeStack = new ListNodeStack();
		
		for(int i=0; i<5; i++) {
			listNodeStack.push(i);
		}
		listNodeStack.print();
		listNodeStack.pop();
		listNodeStack.print();
	}
}
300x250

์ฝ”๋“œ