Bağlı Listeler

package main

import (
	"fmt"
	"strings"
)

type Node[T any] struct {
	Value T
	Next  *Node[T]
}

type List[T comparable] struct {
	head *Node[T]
	tail *Node[T] // sona eklemeyi O(1) yapmak için
	size int
}

func (l *List[T]) Len() int { return l.size }

// PushFront: O(1)
func (l *List[T]) PushFront(v T) {
	n := &Node[T]{Value: v, Next: l.head}
	l.head = n
	if l.tail == nil {
		l.tail = n
	}
	l.size++
}

// PushBack: tail işaretçisi sayesinde O(1)
func (l *List[T]) PushBack(v T) {
	n := &Node[T]{Value: v}
	if l.tail == nil {
		l.head, l.tail = n, n
	} else {
		l.tail.Next = n
		l.tail = n
	}
	l.size++
}

// PopFront: O(1)
func (l *List[T]) PopFront() (T, bool) {
	var zero T
	if l.head == nil {
		return zero, false
	}
	n := l.head
	l.head = n.Next
	if l.head == nil {
		l.tail = nil
	}
	n.Next = nil // çöp toplayıcıya yardım et
	l.size--
	return n.Value, true
}

// Find: O(n)
func (l *List[T]) Find(v T) (*Node[T], int) {
	for n, i := l.head, 0; n != nil; n, i = n.Next, i+1 {
		if n.Value == v {
			return n, i
		}
	}
	return nil, -1
}

// Remove: değeri eşleşen ilk düğümü siler, O(n)
func (l *List[T]) Remove(v T) bool {
	var prev *Node[T]
	for n := l.head; n != nil; n = n.Next {
		if n.Value != v {
			prev = n
			continue
		}
		if prev == nil {
			l.head = n.Next
		} else {
			prev.Next = n.Next
		}
		if n == l.tail {
			l.tail = prev
		}
		n.Next = nil
		l.size--
		return true
	}
	return false
}

func (l *List[T]) String() string {
	var sb strings.Builder
	sb.WriteString("[")
	for n := l.head; n != nil; n = n.Next {
		if n != l.head {
			sb.WriteString(" → ")
		}
		fmt.Fprint(&sb, n.Value)
	}
	sb.WriteString("]")
	return sb.String()
}

func main() {
	var l List[int]

	l.PushBack(20)
	l.PushBack(30)
	l.PushFront(10)
	fmt.Println("liste:", l.String(), "uzunluk:", l.Len())

	if node, idx := l.Find(20); node != nil {
		fmt.Printf("20 bulundu: indeks %d, değer %d\n", idx, node.Value)
	}
	_, notFound := l.Find(99)
	fmt.Println("99 indeksi:", notFound)

	v, _ := l.PopFront()
	fmt.Println("baştan çıkan:", v, "kalan:", l.String())

	fmt.Println("30 silindi mi:", l.Remove(30), "→", l.String(), "uzunluk:", l.Len())
	fmt.Println("boş listeden çekme:", func() bool { _, ok := (&List[int]{}).PopFront(); return ok }())
}

package main

import (
	"fmt"
	"strings"
)

type DNode[T any] struct {
	Value      T
	Prev, Next *DNode[T]
}

type DoublyList[T any] struct {
	head, tail *DNode[T]
	size       int
}

func (l *DoublyList[T]) Len() int { return l.size }

func (l *DoublyList[T]) PushBack(v T) *DNode[T] {
	n := &DNode[T]{Value: v, Prev: l.tail}
	if l.tail != nil {
		l.tail.Next = n
	} else {
		l.head = n
	}
	l.tail = n
	l.size++
	return n
}

func (l *DoublyList[T]) PushFront(v T) *DNode[T] {
	n := &DNode[T]{Value: v, Next: l.head}
	if l.head != nil {
		l.head.Prev = n
	} else {
		l.tail = n
	}
	l.head = n
	l.size++
	return n
}

// RemoveNode: elindeki düğümü O(1) siler — çift yönlü listenin asıl gücü
func (l *DoublyList[T]) RemoveNode(n *DNode[T]) {
	if n == nil {
		return
	}
	if n.Prev != nil {
		n.Prev.Next = n.Next
	} else {
		l.head = n.Next
	}
	if n.Next != nil {
		n.Next.Prev = n.Prev
	} else {
		l.tail = n.Prev
	}
	n.Prev, n.Next = nil, nil
	l.size--
}

func (l *DoublyList[T]) Forward() string {
	var parts []string
	for n := l.head; n != nil; n = n.Next {
		parts = append(parts, fmt.Sprint(n.Value))
	}
	return strings.Join(parts, " ⇄ ")
}

func (l *DoublyList[T]) Backward() string {
	var parts []string
	for n := l.tail; n != nil; n = n.Prev {
		parts = append(parts, fmt.Sprint(n.Value))
	}
	return strings.Join(parts, " ⇄ ")
}

func main() {
	var l DoublyList[string]

	l.PushBack("b")
	middle := l.PushBack("c")
	l.PushBack("d")
	l.PushFront("a")

	fmt.Println("ileri :", l.Forward())
	fmt.Println("geri  :", l.Backward())
	fmt.Println("uzunluk:", l.Len())

	l.RemoveNode(middle) // düğüm elimizde: O(1)
	fmt.Println("c silindi:", l.Forward(), "uzunluk:", l.Len())

	l.RemoveNode(l.head)
	l.RemoveNode(l.tail)
	fmt.Println("uçlar silindi:", l.Forward(), "uzunluk:", l.Len())
}

package main

import "fmt"

type CNode struct {
	Value int
	Next  *CNode
}

// newCircular, 1..n değerlerini içeren dairesel bir liste kurar.
func newCircular(n int) *CNode {
	if n < 1 {
		return nil
	}
	head := &CNode{Value: 1}
	tail := head
	for i := 2; i <= n; i++ {
		tail.Next = &CNode{Value: i}
		tail = tail.Next
	}
	tail.Next = head // daireyi kapat
	return head
}

// josephus, her k'ıncı kişiyi eleyerek son kalanı bulur.
func josephus(n, k int) (int, []int) {
	head := newCircular(n)
	if head == nil {
		return 0, nil
	}

	// Silme için bir önceki düğüme ihtiyaç var
	prev := head
	for prev.Next != head {
		prev = prev.Next
	}

	var eliminated []int
	current := head
	for current.Next != current { // tek kişi kalana kadar
		for range k - 1 {
			prev, current = current, current.Next
		}
		eliminated = append(eliminated, current.Value)
		prev.Next = current.Next
		current = prev.Next
	}
	return current.Value, eliminated
}

func main() {
	// Daireyi iki tur gez
	head := newCircular(5)
	fmt.Print("iki tur: ")
	for n, i := head, 0; i < 10; n, i = n.Next, i+1 {
		fmt.Print(n.Value, " ")
	}
	fmt.Println()

	survivor, order := josephus(7, 3)
	fmt.Println("elenme sırası:", order)
	fmt.Println("hayatta kalan:", survivor)

	survivor2, _ := josephus(10, 2)
	fmt.Println("n=10, k=2 için hayatta kalan:", survivor2)
}

package main

import (
	"fmt"
	"strings"
)

type Node struct {
	Value int
	Next  *Node
}

func build(values ...int) *Node {
	dummy := &Node{}
	tail := dummy
	for _, v := range values {
		tail.Next = &Node{Value: v}
		tail = tail.Next
	}
	return dummy.Next
}

func show(head *Node) string {
	var parts []string
	for n := head; n != nil; n = n.Next {
		parts = append(parts, fmt.Sprint(n.Value))
	}
	if len(parts) == 0 {
		return "boş"
	}
	return strings.Join(parts, " → ")
}

// reverse: iteratif, O(n) zaman, O(1) ek bellek
func reverse(head *Node) *Node {
	var prev *Node
	for cur := head; cur != nil; {
		next := cur.Next // bağlantıyı kaybetmeden önce sakla
		cur.Next = prev  // yönü çevir
		prev = cur       // ilerle
		cur = next
	}
	return prev
}

// reverseRecursive: özyinelemeli, O(n) zaman, O(n) stack belleği
func reverseRecursive(head *Node) *Node {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseRecursive(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

func main() {
	list := build(1, 2, 3, 4, 5)
	fmt.Println("özgün:   ", show(list))

	reversed := reverse(list)
	fmt.Println("ters:    ", show(reversed))

	again := reverseRecursive(reversed)
	fmt.Println("tekrar:  ", show(again))

	fmt.Println("tek eleman:", show(reverse(build(42))))
	fmt.Println("boş liste: ", show(reverse(nil)))
}

package main

import "fmt"

type Node struct {
	Value int
	Next  *Node
}

func build(values ...int) *Node {
	dummy := &Node{}
	tail := dummy
	for _, v := range values {
		tail.Next = &Node{Value: v}
		tail = tail.Next
	}
	return dummy.Next
}

// nodeAt, i. düğümü döndürür (döngü kurmak için).
func nodeAt(head *Node, i int) *Node {
	for n := head; n != nil; n = n.Next {
		if i == 0 {
			return n
		}
		i--
	}
	return nil
}

// hasCycle: Floyd'un tavşan-kaplumbağa algoritması. O(n) zaman, O(1) bellek.
func hasCycle(head *Node) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

// cycleStart, döngünün başladığı düğümü bulur.
func cycleStart(head *Node) *Node {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow != fast {
			continue
		}
		// Buluşma noktasından ve baştan aynı hızla ilerlemek
		// tam olarak döngünün başında buluşur.
		p := head
		for p != slow {
			p = p.Next
			slow = slow.Next
		}
		return p
	}
	return nil
}

// middle, listenin orta düğümünü tek geçişte bulur.
func middle(head *Node) *Node {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

func main() {
	clean := build(1, 2, 3, 4, 5, 6)
	fmt.Println("temiz listede döngü:", hasCycle(clean))
	fmt.Println("orta düğüm:", middle(clean).Value)

	looped := build(1, 2, 3, 4, 5, 6, 7)
	last := nodeAt(looped, 6)
	last.Next = nodeAt(looped, 2) // 3. değere geri bağla

	fmt.Println("döngülü listede döngü:", hasCycle(looped))
	if start := cycleStart(looped); start != nil {
		fmt.Println("döngü şu değerden başlıyor:", start.Value)
	}

	fmt.Println("tek düğümlü kendine bağlı:", func() bool {
		n := &Node{Value: 1}
		n.Next = n
		return hasCycle(n)
	}())
}

package main

import (
	"container/list"
	"fmt"
)

func main() {
	l := list.New()

	l.PushBack("orta")
	back := l.PushBack("son")
	l.PushFront("baş")
	l.InsertBefore("yeni", back) // belirli bir elemanın önüne

	fmt.Print("liste: ")
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Println("| uzunluk:", l.Len())

	// Eleman elindeyse silme O(1)
	l.Remove(back)

	fmt.Print("silmeden sonra: ")
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Println()

	// Değerler any olduğu için tip iddiası gerekir
	if s, ok := l.Front().Value.(string); ok {
		fmt.Println("ilk eleman uzunluğu:", len(s))
	}

	// Elemanı listenin başına taşımak: LRU'nun temel işlemi
	l.MoveToFront(l.Back())
	fmt.Print("taşımadan sonra: ")
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Println()
}