コンテンツにスキップ

リスト構造

リンクを追加
出典: フリー教科書『ウィキブックス（Wikibooks）』

リスト構造は、コンピュータ科学でデータを格納するための基本的なデータ構造の一つです。要素が順序付けされ、一つの要素から次の要素へのポインタ（参照）が繋がっています。これにより、データの挿入や削除が効率的に行えます。リストには単方向リストと双方向リストの２つの主要な種類があります。単方向リストでは、各要素が次の要素へのポインタを持ちますが、双方向リストでは前後の要素へのポインタを持ちます。リスト構造は、プログラミング言語やデータベースなどのさまざまなアプリケーションで幅広く使用されています。

リスト構造の基本

[編集]

リスト構造の基本的な性質は、挿入や削除が容易である反面、ランダムアクセスが効率的ではないことです。リストはポインタによって要素がつながっているため、要素の挿入や削除は、単にポインタの再配置を行うだけで済みます。このため、挿入や削除の時間複雑度はO(1)です。一方、ランダムアクセスは、要素を順番に辿る必要があるため、時間複雑度はO(n)になります。これは、配列の場合と比較して効率が悪い点です。配列では、インデックスによるランダムアクセスがO(1)で実現されますが、挿入や削除は要素の移動が必要であり、その場合の時間複雑度はO(n)になります。したがって、リスト構造と配列は、それぞれ異なる操作において利点を持ちます。

単方向連結リスト

[編集]

単方向連結リスト（Singly Linked List）は、データを連続したノードに格納し、各ノードが次のノードへの参照を持つデータ構造です。各ノードはデータと次のノードへのポインタ（参照）から構成されます。最後のノードは通常、次のノードへの参照がないことを示す特別な値（通常は null や nil）を持ちます。

以下は、単方向連結リストの特徴です。

  1. 単方向性: 各ノードが次のノードへの参照のみを持ち、逆方向の参照を持たないため、データを順方向にのみ走査できます。
  2. 動的なサイズ変更: リストの先頭への挿入や削除が容易であり、動的なサイズ変更が可能です。先頭への挿入や削除は O(1) の時間で実行できます。
  3. 連続したメモリ領域を必要としない: リストの各ノードはメモリ上で非連続的に配置され、挿入や削除操作によってメモリの断片化が発生しません。
  4. ランダムアクセスの非効率性: リストの要素にランダムアクセスする際には、先頭から順番にノードをたどる必要があるため、平均的な時間計算量は O(n) となります。
  5. スタックやキューとしての利用: 先頭への挿入や削除が効率的であるため、スタックやキューなどのデータ構造として利用されることがあります。

単方向連結リストは、データの挿入と削除が頻繁に行われる場合や、ランダムアクセスが少ない場合に適しています。しかし、要素の検索やランダムアクセスが頻繁に必要な場合には、他のデータ構造（例えば、配列や二分木など）の方が適していることがあります。

Ruby

[編集]
sll.rb
# 単方向連結リストの実装
class SinglyLinkedList
  include Enumerable

  # ListNode は単方向連結リスト内のノード。
  ListNode = Struct.new(:data, :next)
  
  # 単方向連結リストを初期化します。
  #
  # *args - 初期化時の引数、配列または整数が指定されることがあります。
  #         - 配列の場合はその要素を順にリストに追加します。
  #         - 整数の場合は、0からその数までの整数をリストに追加します。
  #         - ブロックが与えられた場合は、それぞれの要素に対してブロックを適用して追加します。
  def initialize(*args, &block)
    @head = nil
    case [args, block]
    in [Array => ary], nil
      ary.each{ push _1 }
    in [Array => ary], block
      ary.each{ push block[_1] }
    in [Integer => size], nil
      raise ArgumentError, "#{self.class}#initialize: #{args.inspect}" if size < 0
      size.times{ push _1 }
    in [Integer => size], block
      raise ArgumentError, "#{self.class}#initialize: #{args.inspect}" if size < 0
      size.times{ push block[_1] }
    in [Integer => size, val], nil
      raise ArgumentError, "#{self.class}#initialize: #{args.inspect}" if size < 0
      size.times{ push val }
    in [], nil
    else
      raise ArgumentError, "#{self.class}#initialize: #{args.inspect} #{block && "block_given!"}"
    end
  end

  # リストの先頭に要素を追加します。
  #
  # data - リストに追加するデータ。
  #
  # Returns self.
  def unshift(data)
    @head = ListNode.new(data, @head)
    self
  end
  alias prepend unshift

  # リストの末尾に要素を追加します。
  #
  # data - リストに追加するデータ。
  #
  # Returns self.
  def push(data)
    if @head.nil?
      @head = ListNode.new(data)
    else
      current = @head
      current = current.next until current.next.nil?
      current.next = ListNode.new(data)
    end
    self
  end
  alias append push

  # リストの先頭の要素を取り出します。
  def shift(*args)
    case args
    in [size] => a if size.is_a?(Integer)
      raise ArgumentError, "#{self.class}##{__method__}: #{args.inspect}" if size < 0
      return Array.new(size) { send(__method__) }
    in []
    else
      raise ArgumentError, "#{self.class}##{__method__}: #{args.inspect}"
    end
    data = @head&.data
    @head = @head&.next
    data
  end

  # リストの末尾の要素を取り出します。
  def pop(*args)
    case args
    in [size] => a if size.is_a?(Integer)
      raise ArgumentError, "#{self.class}##{__method__}: #{args.inspect}" if size < 0
      return Array.new(size) { send(__method__) }
      return ary
    in []
    else
      raise ArgumentError, "#{self.class}##{__method__}: #{args.inspect}"
    end
    return nil if @head.nil?

    if @head.next.nil?
      data = @head.data
      @head = nil
      return data
    end
    current = @head
    last = current
    until current.next.nil?
      last = current
      current = current.next
    end
    data = current.data
    last.next = nil
    data
  end

  # リストをトラバースして各ノードに対してブロックを適用します。
  #
  # Returns nothing.
  def each
    return to_enum unless block_given?

    current = @head
    while current
      yield(current.data) if block_given?
      current = current.next
    end
    self
  end

  # リストの文字列表現を返します。
  #
  # Returns リストを表す文字列。
  def to_s = "(#{to_a.join(' ')})"

  # リストのデバッグ用表現を返します。
  #
  # Returns デバッグ用表現を表す文字列。
  def inspect = "#{self.class}(#{to_a.join ', '})"
end
def SinglyLinkedList(args, &block) = SinglyLinkedList.new(args, &block)

require 'minitest/spec'

describe SinglyLinkedList do
  let(:list0) { SinglyLinkedList.new }
  let(:list3) { SinglyLinkedList.new([1, 2, 3]) }
  
  describe '#initialize' do
    it 'initializes an empty list if no arguments are provided' do
      list = SinglyLinkedList.new
      expect(list.to_a).must_equal []
    end

    it 'initializes with an array' do
      list = SinglyLinkedList.new([1, 2, 3])
      expect(list.to_a).must_equal [1, 2, 3]
    end

    it 'initializes with an array with block' do
      list = SinglyLinkedList.new([1, 2, 3]){|i| 2 * i }
      expect(list.to_a).must_equal [2, 4, 6]
    end

    it 'initializes with a block' do
      list = SinglyLinkedList.new(3) { |i| i + 1 }
      expect(list.to_a).must_equal [1, 2, 3]
    end

    it 'initializes with a block' do
      list = SinglyLinkedList.new(3, 42)
      expect(list.to_a).must_equal [42, 42, 42]
    end

    it 'raises ArgumentError if negative size is provided' do
      expect { SinglyLinkedList.new(-1) }.must_raise ArgumentError
    end

    it 'raises ArgumentError if unexpected arguments are provided' do
      expect { SinglyLinkedList.new('unexpected') }.must_raise ArgumentError
    end
  end

  describe '#unshift' do
    it 'adds elements to the beginning of the list' do
      list0.unshift(3).unshift(2).unshift(1)
      expect(list0.to_a).must_equal [1, 2, 3]
    end
  end

  describe '#push' do
    it 'adds elements to the end of the list' do
      list0.push(1).push(2).push(3)
      expect(list0.to_a).must_equal [1, 2, 3]
    end
  end

  describe '#shift' do
    it 'removes and returns the first element from the list' do
      expect(list3.shift).must_equal 1
      expect(list3.to_a).must_equal [2, 3]
    end

    it 'multi shift from the list' do
      expect(list3.shift(2)).must_equal [1, 2]
      expect(list3.to_a).must_equal [3]
    end

    it 'Ill. shift args.' do
      expect { list3.shift('unexpected') }.must_raise ArgumentError
    end

    it 'returns nil if the list is empty' do
      expect(list0.shift).must_be_nil
    end
  end

  describe '#pop' do
    it 'removes and returns the last element from the list' do
      expect(list3.pop).must_equal 3
      expect(list3.to_a).must_equal [1, 2]
    end

    it 'multi pop from the list' do
      expect(list3.pop(2)).must_equal [3, 2]
      expect(list3.to_a).must_equal [1]
    end

    it 'Ill. pop args.' do
      expect { list3.shift('unexpected') }.must_raise ArgumentError
    end

    it 'returns nil if the list is empty' do
      expect(list0.pop).must_be_nil
    end
  end

  describe '#each' do
    it 'iterates over each element in the list' do
      result = []
      list3.each { |x| result << x }
      expect(result).must_equal [1, 2, 3]
    end

    it 'returns an enumerator if no block is given' do
      expect(list3.each).must_be_kind_of Enumerator
    end
  end

  describe '#to_s' do
    it 'returns a string representation of the list' do
      expect(list3.to_s).must_equal "(1 2 3)"
    end
  end

  describe '#inspect' do
    it 'returns a debug representation of the list' do
      expect(list3.inspect).must_equal "SinglyLinkedList(1, 2, 3)"
    end
  end
end
    
Minitest.run if $PROGRAM_NAME == __FILE__

このコードは、単方向連結リストを実装しています。単方向連結リストは、各要素が次の要素への参照を持つデータ構造です。以下は、コードの主な機能とクラスの構造についての解説です。

  1. SinglyLinkedList クラス:
    • Enumerable モジュールをインクルードしており、繰り返し処理を行うためのメソッドを提供しています。
    • ListNode という構造体を定義しています。これは単方向連結リスト内のノードを表します。
    • initialize メソッド: 空の単方向連結リストを初期化します。
    • unshift(data) メソッド: リストの先頭に要素を追加します。
    • push(data) メソッド: リストの末尾に要素を追加します。
    • shift(n) メソッド: リストの先頭の要素を取り出します。
    • pop(n) メソッド: リストの末尾の要素を取り出します。
    • each メソッド: リストをトラバースして各ノードに対してブロックを適用します。
    • to_s メソッド: リストの文字列表現を返します。
    • inspect メソッド: リストのデバッグ用表現を返します。

このコードは、単方向連結リストの基本的な操作を提供し、それらが期待通りに機能することを保証するテストを提供しています。テストによって、コードの正しさが検証されています。

Rust

[編集]
list.rs
use std::fmt;

#[derive(Debug)]
pub struct ListNode<T> {
    data: T,
    next: Option<Box<ListNode<T>>>,
}

impl<T> ListNode<T> {
    pub fn new(data: T) -> Self {
        ListNode { data, next: None }
    }
}

pub struct SinglyLinkedList<T> {
    head: Option<Box<ListNode<T>>>,
}

impl<T> SinglyLinkedList<T> {
    pub fn new() -> Self {
        SinglyLinkedList { head: None }
    }

    pub fn push(&mut self, data: T) -> &mut Self {
        let new_node = Box::new(ListNode::new(data));
        if let Some(ref mut head) = self.head {
            let mut current = head;
            while let Some(ref mut next) = current.next {
                current = next;
            }
            current.next = Some(new_node);
        } else {
            self.head = Some(new_node);
        }
        self
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.data
        })
    }

    pub fn shift(&mut self) -> Option<T> {
        self.head.take().map(|mut node| {
            self.head = node.next.take();
            node.data
        })
    }

    pub fn unshift(&mut self, data: T) -> &mut Self {
        let new_node = Box::new(ListNode::new(data));
        let mut new_head = Some(new_node);
        std::mem::swap(&mut self.head, &mut new_head);
        if let Some(ref mut head) = self.head {
            head.next = new_head;
        }
        self
    }

    pub fn iter(&self) -> ListIterator<'_, T> {
        ListIterator {
            current: self.head.as_ref().map(|node| &**node),
        }
    }

    pub fn to_vec(&self) -> Vec<&T> {
        let mut result = Vec::new();
        let mut current = self.head.as_ref().map(|node| &**node);
        while let Some(node) = current {
            result.push(&node.data);
            current = node.next.as_ref().map(|next| &**next);
        }
        result
    }
}

pub struct ListIterator<'a, T> {
    current: Option<&'a ListNode<T>>,
}

impl<'a, T> Iterator for ListIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.current {
            Some(node) => {
                self.current = node.next.as_ref().map(|next| &**next);
                Some(&node.data)
            }
            None => None,
        }
    }
}

impl<T: fmt::Debug> fmt::Debug for SinglyLinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "SinglyLinkedList[")?;
        let mut current = self.head.as_ref().map(|node| &**node);
        while let Some(node) = current {
            write!(f, "{:?}", node.data)?;
            current = node.next.as_ref().map(|next| &**next);
            if current.is_some() {
                write!(f, " -> ")?;
            }
        }
        write!(f, "]")
    }
}

impl<T: fmt::Display> fmt::Display for SinglyLinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "(")?;
        let mut current = self.head.as_ref().map(|node| &**node);
        while let Some(node) = current {
            write!(f, "{}", node.data)?;
            current = node.next.as_ref().map(|next| &**next);
            if current.is_some() {
                write!(f, " ")?;
            }
        }
        write!(f, ")")
    }
}

fn main() {
    let mut list = SinglyLinkedList::new();
    list.push(1).push(2).push(3).push(4).push(5);
    
    println!("{:?}", list);  // => "SinglyLinkedList[1 -> 2 -> 3 -> 4 -> 5]"
    println!("{}", list);     // => "(1 2 3)"
    println!("{:?}", list.to_vec()); // => [1, 2, 3]
    
    let doubled_filtered_numbers: Vec<_> = list
        .iter()
        .filter(|&x| *x % 2 == 0)
        .map(|x| x * 2)
        .collect();

    println!("{:?}", doubled_filtered_numbers); // => [4, 8]
    
    let mut list = SinglyLinkedList::new();
    list.push(1).push(2).push(3);
    list.unshift(8);
    println!("{}", list);         // => "(8 1 2 3)"
    println!("{:?}", list.pop()); // => Some(8)
    println!("{}", list);         // => "(8 1 2 3)"
    println!("{:?}", list.shift()); // => Some(1)
    println!("{}", list);         // => "(2 3)"
}

このRustのコードは、単方向連結リストを表すデータ構造を実装しています。以下の要素からなります：

  • ListNode<T>: リスト内の各ノードを表す構造体です。データ T と次のノードへの参照を持ちます。
  • SinglyLinkedList<T>: 単方向連結リスト全体を表す構造体で、リストの先頭ノードへの参照を持ちます。ノードの追加や反復処理のためのメソッドを提供します。
  • ListIterator<'a, T>: リストを反復処理するイテレータです。Iterator トレイトを実装しており、次の要素を返す next メソッドを提供します。

また、SinglyLinkedList<T> には、デバッグ用のフォーマットや表示用のフォーマットが実装されています。これにより、println! マクロなどでリストの内容を出力できます。

最後に、main 関数では SinglyLinkedList を使用して、リストを作成し、要素の追加、デバッグ表示、通常の表示、イテレーション、フィルタリング、マッピングなどが行われています。

Go

[編集]
list.go
package main

import (
	"fmt"
)

// ListNode は単方向連結リスト内のノードを表します。
type ListNode struct {
	data int
	next *ListNode
}

// SinglyLinkedList は単方向連結リストを表します。
type SinglyLinkedList struct {
	head *ListNode
}

// NewSinglyLinkedList は新しい SinglyLinkedList インスタンスを作成します。
func NewSinglyLinkedList(data ...int) *SinglyLinkedList {
	list := &SinglyLinkedList{}
	for _, d := range data {
		list.Push(d)
	}
	return list
}

// unshift はリストの先頭に要素を追加します。
func (list *SinglyLinkedList) Unshift(data int) {
	list.head = &ListNode{data, list.head}
}

// push はリストの末尾に要素を追加します。
func (list *SinglyLinkedList) Push(data int) *SinglyLinkedList {
	if list.head == nil {
		list.head = &ListNode{data, nil}
		return list
	}
	tail := list.findTail()
	tail.next = &ListNode{data, nil}
	return list
}

// findTail はリストの末尾の要素を取得します。
func (list *SinglyLinkedList) findTail() *ListNode {
	if list.head == nil {
		return nil
	}
	current := list.head
	for current.next != nil {
		current = current.next
	}
	return current
}

// Shift はリストの先頭の要素を取り出します。
func (list *SinglyLinkedList) Shift() int {
	if list.head == nil {
		return -1 // エラーを表す値として-1を返す
	}
	data := list.head.data
	list.head = list.head.next
	return data
}

// pop はリストの末尾の要素を取り出します。
func (list *SinglyLinkedList) pop() int {
	if list.head == nil {
		return -1 // エラーを表す値として-1を返す
	}
	if list.head.next == nil {
		data := list.head.data
		list.head = nil
		return data
	}
	current := list.head
	var last *ListNode
	for current.next != nil {
		last = current
		current = current.next
	}
	data := current.data
	last.next = nil
	return data
}

// Iterator は単方向連結リストのイテレータを表します。
type Iterator struct {
	current *ListNode
}

// HasNext は次の要素があるかどうかを返します。
func (it *Iterator) HasNext() bool {
	return it.current != nil
}

// Next は次の要素を返します。
func (it *Iterator) Next() int {
	if it.current != nil {
		data := it.current.data
		it.current = it.current.next
		return data
	}
	return 0
}

// NewIterator は新しいイテレータを作成します。
func (list *SinglyLinkedList) NewIterator() *Iterator {
	return &Iterator{current: list.head}
}

// Map はリスト内の各要素に関数を適用した結果からなるリストを返します。
func (list *SinglyLinkedList) Map(f func(int) int) *SinglyLinkedList {
	result := &SinglyLinkedList{}
	iterator := list.NewIterator()
	for iterator.HasNext() {
		result.Push(f(iterator.Next()))
	}
	return result
}

// Select はリスト内の条件を満たす要素からなるリストを返します。
func (list *SinglyLinkedList) Select(f func(int) bool) *SinglyLinkedList {
	result := &SinglyLinkedList{}
	iterator := list.NewIterator()
	for iterator.HasNext() {
		val := iterator.Next()
		if f(val) {
			result.Push(val)
		}
	}
	return result
}

// Reduce はリストの各要素を結合して単一の値を返します。
func (list *SinglyLinkedList) Reduce(initial int, f func(int, int) int) int {
	accumulator := initial
	iterator := list.NewIterator()
	for iterator.HasNext() {
		accumulator = f(accumulator, iterator.Next())
	}
	return accumulator
}

// String はリストの文字列表現を返します。
func (list *SinglyLinkedList) String() string {
	var result string
	iterator := list.NewIterator()
	for iterator.HasNext() {
		result += fmt.Sprintf("%d", iterator.Next())
		if iterator.HasNext() {
			result += " "
		}
	}
	return fmt.Sprintf("(%s)", result)
}

// Inspect はリストのデバッグ用表現を返します。
func (list *SinglyLinkedList) Inspect() string {
	var result string
	iterator := list.NewIterator()
	for iterator.HasNext() {
		result += fmt.Sprintf("%d -> ", iterator.Next())
	}
	return result + "nil"
}

// ToSlice はリストの配列表現を返します。
func (list *SinglyLinkedList) ToSlice() []int {
	var slice []int

	iterator := list.NewIterator()
	for iterator.HasNext() {
		slice = append(slice, iterator.Next())
	}

	return slice
}

func main() {
	// リスト構造の操作
	list := SinglyLinkedList{}
	list.Push(1).Push(2).Push(3)

	// リストのデバッグ用表現を表示
	fmt.Println(list.Inspect()) // => "1 -> 2 -> 3 -> nil"

	// Enumerableメソッドの利用例
	mapped := list.Map(func(x int) int { return x * 2 }).ToSlice()
	fmt.Println(mapped) // => [2 4 6]
	filtered := list.Select(func(x int) bool { return x%2 == 0 }).ToSlice()
	fmt.Println(filtered) // => [2]
	sum := list.Reduce(0, func(acc, x int) int { return acc + x })
	fmt.Println(sum) // => 6

	// メソッドチェーンの利用例
	chained := list.Map(func(x int) int { return x * 2 }).
		Select(func(x int) bool { return x < 5 }).
		ToSlice()
	fmt.Println(chained) // => [2 4]

	iterator := list.NewIterator()
	for iterator.HasNext() {
		fmt.Printf("%d ", iterator.Next())
	}
	fmt.Println() // 改行
}

Iterator 構造体は、リスト内の要素に順番にアクセスするための手段を提供します。Next メソッドは、イテレータが現在指している要素を返し、次の要素に進みます。また、Iterate メソッドは、単方向連結リストのイテレータを生成するためのメソッドです。これにより、リスト内の要素に順番にアクセスするためのイテレータが提供されます。

Map、Select、Reduce メソッドでは、Iterator パターンが活用されています。これらのメソッドは、リスト内の要素に対して関数を適用したり、条件を満たす要素を選択したり、要素を結合したりするために、イテレータが使用されています。これにより、コレクション内の要素に対する操作が効率的に実装されています。

Iterator パターンの利点は、データ構造の内部構造に依存せずに要素にアクセスできることです。また、反復処理が抽象化され、コードの再利用性が向上します。さらに、Iterator を使用することで、リストの要素に順番にアクセスするための操作が明確になり、コードがよりシンプルで理解しやすくなります。

Haskell

[編集]
list.hs
data ListNode a = ListNode {
    listData :: a,
    nextNode :: Maybe (ListNode a)
}

data SinglyLinkedList a = SinglyLinkedList {
    headNode :: Maybe (ListNode a)
}

-- 空の単方向リンクリストを初期化します。
emptyList :: SinglyLinkedList a
emptyList = SinglyLinkedList { headNode = Nothing }

-- リストの末尾に要素を追加します。
push :: SinglyLinkedList a -> a -> SinglyLinkedList a
push list value = case headNode list of
    Nothing -> list { headNode = Just $ ListNode value Nothing }
    Just node -> list { headNode = Just $ appendNode node }
    where appendNode (ListNode val next) = ListNode val (Just (appendNode' next))
          appendNode' Nothing = ListNode value Nothing
          appendNode' (Just n) = ListNode (listData n) (Just (appendNode' (nextNode n)))

-- リストの文字列表現を返します。
toString :: Show a => SinglyLinkedList a -> String
toString list = "(" ++ formatList (headNode list) ++ ")"
    where
        formatList Nothing = ""
        formatList (Just node) = show (listData node) ++ " " ++ formatList (nextNode node)

-- リストのデバッグ用表現を返します。
inspect :: Show a => SinglyLinkedList a -> String
inspect list = formatList (headNode list)
    where
        formatList Nothing = "nil"
        formatList (Just node) = show (listData node) ++ " -> " ++ formatList (nextNode node)

-- リストの配列表現を返します。
toArray :: SinglyLinkedList a -> [a]
toArray list = formatList (headNode list)
    where
        formatList Nothing = []
        formatList (Just node) = listData node : formatList (nextNode node)

main :: IO ()
main = do
    -- リスト構造の操作
    let list = foldl push emptyList [1, 2, 3]
    putStrLn $ inspect list  -- => "1 -> 2 -> 3 -> nil"
    putStrLn $ toString list -- => "(1 2 3)"
    print $ toArray list     -- => [1, 2, 3]

JavaScript

[編集]
list.js
class ListNode {
    constructor(data) {
        this.data = data;
        this.nextNode = null;
    }
}

class SinglyLinkedList {
    constructor() {
        this.head = null;
    }

    push(data) {
        const newNode = new ListNode(data);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.nextNode) {
                current = current.nextNode;
            }
            current.nextNode = newNode;
        }
        // メソッドチェインをサポートするためにthisを返す
        return this;
    }

    *[Symbol.iterator]() {
        let current = this.head;
        while (current) {
            yield current.data;
            current = current.nextNode;
        }
    }

    forEach(callback, thisArg) {
        for (const item of this) {
            callback.call(thisArg, item);
        }
    }

    map(callback, thisArg) {
        const newArray = [];
        for (const item of this) {
            newArray.push(callback.call(thisArg, item));
        }
        return newArray;
    }

    filter(callback, thisArg) {
        const newArray = [];
        for (const item of this) {
            if (callback.call(thisArg, item)) {
                newArray.push(item);
            }
        }
        return newArray;
    }

    reduce(callback, initialValue) {
        let accumulator = initialValue;
        for (const item of this) {
            accumulator = callback(accumulator, item);
        }
        return accumulator;
    }

    every(callback, thisArg) {
        for (const item of this) {
            if (!callback.call(thisArg, item)) {
                return false;
            }
        }
        return true;
    }

    find(callback, thisArg) {
        for (const item of this) {
            if (callback.call(thisArg, item)) {
                return item;
            }
        }
        return undefined;
    }

    findIndex(callback, thisArg) {
        let index = 0;
        for (const item of this) {
            if (callback.call(thisArg, item)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    findLast(callback, thisArg) {
        let found;
        for (const item of this) {
            if (callback.call(thisArg, item)) {
                found = item;
            }
        }
        return found;
    }

    findLastIndex(callback, thisArg) {
        let lastIndex = -1;
        let index = 0;
        for (const item of this) {
            if (callback.call(thisArg, item)) {
                lastIndex = index;
            }
            index++;
        }
        return lastIndex;
    }

    flatMap(callback, thisArg) {
        const newArray = [];
        for (const item of this) {
            const result = callback.call(thisArg, item);
            if (Array.isArray(result)) {
                newArray.push(...result);
            } else {
                newArray.push(result);
            }
        }
        return newArray;
    }

    some(callback, thisArg) {
        for (const item of this) {
            if (callback.call(thisArg, item)) {
                return true;
            }
        }
        return false;
    }
}

// リスト構造の操作
const list = new SinglyLinkedList()
    .push(1)
    .push(2)
    .push(3);

// メソッドチェインでの操作
const chainedArray = list
    .filter(item => item % 2 === 0)
    .map(item => item * 2);
console.log(chainedArray); // => [4]

// for...of ループでの反復処理
for (const item of list) {
    console.log(item);
}

// Spread 演算子を使った反復処理
const array = [...list];
console.log(array); // => [1, 2, 3]

// every
const allGreaterThanZero = list.every(item => item > 0);
console.log(allGreaterThanZero); // => true

// filter
const filteredArray = list.filter(item => item % 2 === 0);
console.log(filteredArray); // => [2]

// find
const foundItem = list.find(item => item === 2);
console.log(foundItem); // => 2

// findIndex
const foundIndex = list.findIndex(item => item === 2);
console.log(foundIndex); // => 1

// findLast
const foundLastItem = list.findLast(item => item > 1);
console.log(foundLastItem); // => 3

// findLastIndex
const foundLastIndex = list.findLastIndex(item => item > 1);
console.log(foundLastIndex); // => 2

// flatMap
const flattenedArray = list.flatMap(item => [item, item * 2]);
console.log(flattenedArray); // => [1, 2, 2, 4, 3, 6]

// some
const anyGreaterThanTwo = list.some(item => item > 2);
console.log(anyGreaterThanTwo); // => true

C

[編集]
list.c
#include <stdio.h>
#include <stdlib.h>

// リストノードの構造体の定義
typedef struct ListNode {
    int data;
    struct ListNode *nextNode;
} ListNode;

// 単方向連結リストの構造体の定義
typedef struct SinglyLinkedList {
    ListNode *head;
} SinglyLinkedList;

// 新しいリストノードを作成する関数
ListNode* createNode(int data) {
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    if (node != NULL) {
        node->data = data;
        node->nextNode = NULL;
    }
    return node;
}

// 空の単方向連結リストを初期化する関数
void initialize(SinglyLinkedList *list) {
    list->head = NULL;
}

// リストの末尾に要素を追加する関数
void push(SinglyLinkedList *list, int data) {
    ListNode *newNode = createNode(data);
    if (list->head == NULL) {
        list->head = newNode;
    } else {
        ListNode *current = list->head;
        while (current->nextNode != NULL) {
            current = current->nextNode;
        }
        current->nextNode = newNode;
    }
}

// リストの文字列表現を返す関数
char* toString(SinglyLinkedList *list) {
    char *result = (char*)malloc(256 * sizeof(char));
    if (result != NULL) {
        ListNode *current = list->head;
        sprintf(result, "(");
        while (current != NULL) {
            char temp[16];
            sprintf(temp, "%d ", current->data);
            strcat(result, temp);
            current = current->nextNode;
        }
        strcat(result, ")\0");
    }
    return result;
}

// リストのデバッグ用表現を返す関数
char* inspect(SinglyLinkedList *list) {
    char *result = (char*)malloc(256 * sizeof(char));
    if (result != NULL) {
        ListNode *current = list->head;
        sprintf(result, "");
        while (current != NULL) {
            char temp[16];
            sprintf(temp, "%d -> ", current->data);
            strcat(result, temp);
            current = current->nextNode;
        }
        strcat(result, "nil\0");
    }
    return result;
}

// リストの配列表現を返す関数
int* toArray(SinglyLinkedList *list) {
    int *array = (int*)malloc(256 * sizeof(int));
    if (array != NULL) {
        ListNode *current = list->head;
        int index = 0;
        while (current != NULL) {
            array[index++] = current->data;
            current = current->nextNode;
        }
        array[index] = -1; // 終端をマークするために -1 を挿入
    }
    return array;
}

int main() {
    // リスト構造の操作
    SinglyLinkedList list;
    initialize(&list);
    push(&list, 1);
    push(&list, 2);
    push(&list, 3);

    // リストの文字列表現を出力
    printf("%s\n", inspect(&list));  // => "1 -> 2 -> 3 -> nil"
    printf("%s\n", toString(&list)); // => "(1 2 3)"

    // リストの配列表現を出力
    int *array = toArray(&list);
    printf("[");
    for (int i = 0; array[i] != -1; ++i) {
        printf("%d ", array[i]);
    }
    printf("]\n");

    // メモリリークを防ぐために配列を解放
    free(array);
    return 0;
}

C++

[編集]
list.C
#include <iostream>
#include <vector>
#include <functional>

// リストノードの構造体の定義
struct ListNode {
    int data;
    ListNode *nextNode;

    ListNode(int data) : data(data), nextNode(nullptr) {}
};

// 単方向連結リストのクラスの定義
class SinglyLinkedList {
private:
    ListNode *head;

public:
    // コンストラクタ
    SinglyLinkedList() : head(nullptr) {}

    // デストラクタ
    ~SinglyLinkedList() {
        ListNode *current = head;
        while (current) {
            ListNode *next = current->nextNode;
            delete current;
            current = next;
        }
    }
    // リストの末尾に要素を追加するメソッド
    void push(int data) {
        if (!head) {
            head = new ListNode(data);
        } else {
            ListNode *current = nullptr;
            for (current = head; current->nextNode; current = current->nextNode) {
                ;
            }
            current->nextNode = new ListNode(data);
        }
    }

    // リストの文字列表現を返すメソッド
    std::string toString() {
        std::string result = "(";
        traverse([&result](int data) {
            result += std::to_string(data) + " ";
        });
        result += ")";
        return result;
    }

    // リストのデバッグ用表現を返すメソッド
    std::string inspect() {
        std::string result;
        traverse([&result](int data) {
            result += std::to_string(data) + " -> ";
        });
        result += "nil";
        return result;
    }

    // リストの配列表現を返すメソッド
    std::vector<int> toArray() {
        std::vector<int> array;
        traverse([&array](int data) {
            array.push_back(data);
        });
        return array;
    }

private:
    // トラバース関数
    void traverse(std::function<void(int)> callback) {
        ListNode *current = nullptr;
        for (current = head;current; current = current->nextNode) {
            callback(current->data);
        }
    }
};

int main() {
    // リスト構造の操作
    SinglyLinkedList list;
    list.push(1);
    list.push(2);
    list.push(3);

    // リストの文字列表現を出力
    std::cout << list.inspect() << std::endl;  // => "1 -> 2 -> 3 -> nil"
    std::cout << list.toString() << std::endl; // => "(1 2 3)"

    // リストの配列表現を出力
    std::vector<int> array = list.toArray();
    std::cout << "[";
    for (auto data : array) {
        std::cout << data << " ";
    }
    std::cout << "]" << std::endl;

    return 0;
}

このプログラムは、単方向連結リストを表現し、さまざまな操作を行うためのものです。以下に、主な部分の解説を提供します。

  1. ListNode構造体:
    • ListNode は、単方向連結リストのノードを表します。
    • data メンバ変数は、ノードが保持する整数値を格納します。
    • nextNode メンバ変数は、次のノードへのポインタを保持します。
  2. SinglyLinkedListクラス:
    • SinglyLinkedList は、単方向連結リストを表すクラスです。
    • head メンバ変数は、リストの先頭ノードを示すポインタです。
    • コンストラクタでは、リストを初期化し、head を nullptr に設定します。
    • デストラクタでは、リストの全てのノードを解放します。
  3. pushメソッド:
    • 新しい要素をリストの末尾に追加するためのメソッドです。
    • リストが空の場合は、新しいノードを作成して head に設定します。
    • リストが空でない場合は、最後のノードまで移動してから新しいノードを追加します。
  4. toStringメソッド:
    • リストの要素を文字列形式で返すメソッドです。
    • traverse メソッドを使用して、各要素を文字列に追加します。
  5. inspectメソッド:
    • デバッグ用のリスト表現を文字列形式で返すメソッドです。
    • traverse メソッドを使用して、各要素とそれに続く矢印 "→" を文字列に追加します。
  6. toArrayメソッド:
    • リストの要素を配列形式で返すメソッドです。
    • traverse メソッドを使用して、各要素を配列に追加します。
  7. traverseメソッド:
    • リストの全ての要素を順番に処理するためのメソッドです。
    • コールバック関数を引数として受け取り、各要素に対してその関数を呼び出します。
  8. main関数:
    • SinglyLinkedList のインスタンスを作成し、いくつかの要素を追加します。
    • inspect メソッド、toString メソッド、および toArray メソッドを使用して、リストの内容を表示します。

これらの要素が組み合わさって、単方向連結リストの作成、操作、表示が行われています。

C#

[編集]
list.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

public class ListNode {
    public int Data { get; set; }
    public ListNode NextNode { get; set; }

    public ListNode(int data) {
        Data = data;
        NextNode = null;
    }
}

public class SinglyLinkedList : IEnumerable<int> {
    private ListNode head;

    public SinglyLinkedList() {
        head = null;
    }

    // リストの末尾に要素を追加する
    public SinglyLinkedList Push(int data) {
        if (head == null) {
            head = new ListNode(data);
        } else {
            ListNode current = head;
            while (current.NextNode != null) {
                current = current.NextNode;
            }
            current.NextNode = new ListNode(data);
        }
        return this;
    }

    // リストの要素を文字列として表現する
    public override string ToString() {
        StringBuilder result = new StringBuilder("(");
        foreach (int data in this) {
            result.Append(data).Append(" ");
        }
        result.Append(")");
        return result.ToString();
    }

    // リストの要素を調査して表現する
    public string Inspect() {
        StringBuilder result = new StringBuilder();
        foreach (int data in this) {
            result.Append(data).Append(" -> ");
        }
        result.Append("nil");
        return result.ToString();
    }

    // リストの要素を配列に変換する
    public List<int> ToArray() {
        List<int> array = new List<int>();
        foreach (int data in this) {
            array.Add(data);
        }
        return array;
    }

    // リストの要素を減算する
    public int Reduce(int initial, Func<int, int, int> func) {
        int accumulator = initial;
        foreach (int data in this) {
            accumulator = func(accumulator, data);
        }
        return accumulator;
    }

    // リストの各要素に関数を適用する
    public SinglyLinkedList Map(Func<int, int> func) {
        SinglyLinkedList result = new SinglyLinkedList();
        foreach (int data in this) {
            result.Push(func(data));
        }
        return result;
    }

    // 条件を満たす要素だけを含む新しいリストを返す
    public SinglyLinkedList Filter(Func<int, bool> predicate) {
        SinglyLinkedList result = new SinglyLinkedList();
        foreach (int data in this) {
            if (predicate(data)) {
                result.Push(data);
            }
        }
        return result;
    }

    // IEnumerable<int> の実装
    public IEnumerator<int> GetEnumerator() {
        ListNode current = head;
        while (current != null) {
            yield return current.Data;
            current = current.NextNode;
        }
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}

class Program {
    static void Main(string[] args) {
        SinglyLinkedList list = new SinglyLinkedList()
            .Push(1)
            .Push(2)
            .Push(3);

        Console.WriteLine(list.Inspect());  // => "1 -> 2 -> 3 -> nil"
        Console.WriteLine(list.ToString()); // => "(1 2 3)"

        List<int> array = list.ToArray();
        Console.Write("[");
        foreach (int item in array) {
            Console.Write(item + " ");
        }
        Console.WriteLine("]");

        int sum = list.Reduce(0, (acc, x) => acc + x);
        Console.WriteLine("Sum: " + sum); // => 6

        SinglyLinkedList mapped = list.Map(x => x * 2);
        Console.WriteLine("Mapped: " + mapped.ToString()); // => "(2 4 6)"

        SinglyLinkedList filtered = list.Filter(x => x % 2 == 0);
        Console.WriteLine("Filtered: " + filtered.ToString()); // => "(2)"
    }
}

Java

[編集]
list.java
import java.util.ArrayList;
import java.util.List;

// ListNode クラスは単方向連結リスト内のノードを表します。
class ListNode {
    // ノードのデータを取得/設定します。
    int data;
    // 次のノードへの参照を取得/設定します。
    ListNode nextNode;

    // 新しいノードを与えられたデータで初期化します。
    ListNode(int data) {
        this.data = data;
        this.nextNode = null;
    }
}

// SinglyLinkedList クラスは単方向連結リストを表します。
class SinglyLinkedList {
    private ListNode head;

    // 空の単方向連結リストを初期化します。
    public SinglyLinkedList() {
        head = null;
    }

    // リストの末尾に要素を追加します。
    public void push(int data) {
        if (head == null) {
            head = new ListNode(data);
        } else {
            ListNode current = head;
            while (current.nextNode != null) {
                current = current.nextNode;
            }
            current.nextNode = new ListNode(data);
        }
    }

    // リストの文字列表現を返します。
    public String toString() {
        StringBuilder result = new StringBuilder("(");
        traverse(data -> result.append(data).append(" "));
        result.append(")");
        return result.toString();
    }

    // リストのデバッグ用表現を返します。
    public String inspect() {
        StringBuilder result = new StringBuilder();
        traverse(data -> result.append(data).append(" -> "));
        result.append("nil");
        return result.toString();
    }

    // リストの配列表現を返します。
    public List<Integer> toArray() {
        List<Integer> array = new ArrayList<>();
        traverse(array::add);
        return array;
    }

    // リストをトラバースして各要素に対して指定されたアクションを実行します。
    public void traverse(java.util.function.Consumer<Integer> action) {
        ListNode current = head;
        while (current != null) {
            action.accept(current.data);
            current = current.nextNode;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        // リスト構造の操作
        SinglyLinkedList list = new SinglyLinkedList();
        list.push(1);
        list.push(2);
        list.push(3);

        // リストの文字列表現を出力
        System.out.println(list.inspect());  // => "1 -> 2 -> 3 -> nil"
        System.out.println(list.toString()); // => "(1 2 3)"

        // リストの配列表現を出力
        List<Integer> array = list.toArray();
        System.out.print("[");
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println("]");
    }
}

このプログラムは、単方向連結リストを表すSinglyLinkedListクラスを実装しています。ListNodeクラスは、単方向連結リスト内のノードを表します。

SinglyLinkedListクラスには次のメソッドが含まれています：

  • push(int data): リストの末尾に要素を追加します。
  • toString(): リストの文字列表現を返します。
  • inspect(): リストのデバッグ用表現を返します。
  • toArray(): リストの配列表現を返します。
  • traverse(java.util.function.Consumer<Integer> action): リストをトラバースして各要素に対して指定されたアクションを実行します。

Mainクラスには、SinglyLinkedListクラスを使用してリスト構造を操作するためのmainメソッドが含まれています。pushメソッドを使用してリストに要素を追加し、inspectメソッドやtoStringメソッドを使用してリストの表現を出力します。また、toArrayメソッドを使用してリストの配列表現を取得し、配列として出力します。

Python3

[編集]
list.py
# SinglyLinkedList クラスは単方向連結リストを表します。
class SinglyLinkedList:
    # ListNode クラスは単方向連結リスト内のノードを表します。
    class ListNode:
        # 空のノードを初期化します。
        def __init__(self, data):
            # ノードのデータを取得/設定します。
            self.data = data
            # 次のノードへの参照を取得/設定します。
            self.next_node = None

    # 空の単方向連結リストを初期化します。
    def __init__(self):
        self.head = None

    # リストの末尾に要素を追加します。
    def push(self, data):
        if self.head is None:
            self.head = self.ListNode(data)
        else:
            current = self.head
            while current.next_node:
                current = current.next_node
            current.next_node = self.ListNode(data)

    # リストの先頭から要素を取り出します。
    def shift(self):
        if self.head is None:
            return None
        else:
            removed_data = self.head.data
            self.head = self.head.next_node
            return removed_data

    # イテレータを使用してリストをトラバースします。
    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next_node

    # リストの文字列表現を返します。
    def __str__(self):
        return f"({' '.join(str(x) for x in self)})"

    # リストのデバッグ用表現を返します。
    def __repr__(self):
        return " -> ".join([repr(x) for x in self] + [repr(None)])

    # リストの長さ
    def __len__(self):
        count = 0
        for _ in self:
            count += 1
        return count

import unittest

class TestSinglyLinkedList(unittest.TestCase):
    def setUp(self):
        self.lst3 = SinglyLinkedList()
        [self.lst3.push(x) for x in [1, 2, 3]]

    def test_empty_list(self):
        lst = SinglyLinkedList()
        self.assertEqual(str(lst), "()")
        self.assertEqual(list(lst), [])
        self.assertEqual(repr(lst), 'None')
        self.assertEqual(len(lst), 0)
        self.assertEqual(lst.shift(), None)

    def test_str(self):
        self.assertEqual(str(self.lst3), '(1 2 3)')

    def test_list(self):
        self.assertEqual(list(self.lst3), [1, 2, 3])

    def test_repr(self):
        self.assertEqual(repr(self.lst3), '1 -> 2 -> 3 -> None')

    def test_len(self):
        lst = SinglyLinkedList()
        self.assertEqual(len(lst), 0)
        self.assertEqual(len(self.lst3), 3)

    def test_push(self):
        lst = SinglyLinkedList()
        lst.push(10)
        self.assertEqual(str(lst), '(10)')
        lst.push(5)
        self.assertEqual(str(lst), '(10 5)')
        lst.push(20)
        self.assertEqual(str(lst), '(10 5 20)')

    def test_shift(self):
        self.assertEqual(self.lst3.shift(), 1)
        self.assertEqual(str(self.lst3), '(2 3)')
        self.assertEqual(self.lst3.shift(), 2)
        self.assertEqual(str(self.lst3), '(3)')
        self.assertEqual(self.lst3.shift(), 3)
        self.assertEqual(str(self.lst3), '()')
        self.assertEqual(self.lst3.shift(), None)
        self.assertEqual(str(self.lst3), '()')

if __name__ == "__main__":
    unittest.main()

Kotlin

[編集]
list.kt
class SinglyLinkedList<T> : Iterable<T> {
    private data class Node<T>(val data: T, var next: Node<T>? = null)

    private var head: Node<T>? = null

    fun unshift(data: T): SinglyLinkedList<T> {
        head = Node(data, head)
        return this
    }

    fun prepend(data: T): SinglyLinkedList<T> {
        return unshift(data)
    }

    fun push(data: T): SinglyLinkedList<T> {
        if (head == null) {
            head = Node(data)
        } else {
            var current = head
            while (current?.next != null) {
                current = current.next
            }
            current?.next = Node(data)
        }
        return this
    }

    fun append(data: T): SinglyLinkedList<T> {
        return push(data)
    }

    fun shift(): T? {
        val data = head?.data
        head = head?.next
        return data
    }

    fun pop(): T? {
        if (head == null) return null
        if (head?.next == null) {
            val data = head?.data
            head = null
            return data
        }
        var current = head
        var last = current
        while (current?.next != null) {
            last = current
            current = current.next
        }
        val data = current!!.data
        last!!.next = null
        return data
    }

    override fun iterator(): Iterator<T> {
        return object : Iterator<T> {
            private var current: Node<T>? = head

            override fun hasNext(): Boolean {
                return current != null
            }

            override fun next(): T {
                val data = current!!.data
                current = current!!.next
                return data
            }
        }
    }

    override fun toString(): String {
        val builder = StringBuilder("(")
        val iterator = iterator()
        while (iterator.hasNext()) {
            builder.append(iterator.next())
            if (iterator.hasNext()) {
                builder.append(" ")
            }
        }
        builder.append(")")
        return builder.toString()
    }

    fun inspect(): String {
        val builder = StringBuilder()
        val iterator = iterator()
        while (iterator.hasNext()) {
            builder.append(iterator.next())
            builder.append(" -> ")
        }
        builder.append("null")
        return builder.toString()
    }
}

fun main() {
    val list = SinglyLinkedList<Int>()

    list.push(1).push(2).push(3)
    println(list.inspect())  // => "1 -> 2 -> 3 -> nil"
    println(list.toString()) // => "(1 2 3)"

    list.unshift(10).unshift(20).unshift(30)
    println(list.toString()) // => "(30 20 10 1 2 3)"

    println(list.shift())    // => 30
    println(list.shift())    // => 20
    println(list.shift())    // => 10

    // Using Iterable-like methods
    println(list.toList())           // => [1, 2, 3]
    println(list.map { it * 2 })     // => [2, 4, 6]
    println(list.filter { it % 2 == 0 }) // => [2]
    println(list.reduceOrNull(Int::plus)) // => 6
    println(list.count())            // => 3
    println(list.all { it < 10 })    // => true
    println(list.any { it < 3 })     // => true
    println(list.minOrNull() to list.maxOrNull())  // => (1, 3)
}

単方向循環リスト

[編集]

単方向循環リスト（Singly Circular Linked List）は、単方向連結リストの一種であり、最後のノードが最初のノードを指すように構成されたデータ構造です。つまり、最後のノードの次のノードへの参照が先頭のノードを指すようになっています。

単方向循環リストは、通常の単方向連結リストに比べて以下の特徴があります。

  1. ループ性: 最後のノードが最初のノードを指すため、リストがループしています。これにより、最後のノードの次のノードを辿ると最初のノードに戻ることができます。
  2. ループの終了条件の省略: 単方向循環リストでは、ループの終了条件を明示的に定義する必要がありません。従って、特定の位置までのループ処理を行う場合に便利です。
  3. 末尾へのアクセスの効率性: リストの末尾のノードにアクセスするために、最後のノードを特定する必要がなくなります。ループがあるため、先頭のノードから次々にノードを辿っていくことで末尾のノードに到達できます。
  4. 無限ループの可能性: 単方向循環リストは無限にループする可能性があります。適切な終了条件を設定しない場合、ループ内での操作が無限に続くことがあります。

単方向循環リストは、環状的なデータ構造を表現したり、特定のアプリケーションやアルゴリズムに使用されることがあります。例えば、ラウンドロビンスケジューリング、キャッシュアルゴリズム、ゲーム開発などで使用されることがあります。

Ruby

[編集]

単方向リストと単方向循環リストの差異は小さいので、SinglyCircularLinkedListはSinglyLinkedListを継承して実装しました。

scll.rb
require_relative "sll.rb"

# 単方向循環リストクラス
class SinglyCircularLinkedList < SinglyLinkedList
  # リストの先頭に要素を追加します。
  #
  # data - リストに追加するデータ。
  #
  # Returns self.
  def unshift(data)
    if @head.nil?
      @head = ListNode.new(data)
      @head.next = @head
    else
      new_node = ListNode.new(data)
      last_node = @head
      last_node = last_node.next while last_node.next != @head
      last_node.next = new_node
      new_node.next = @head
      @head = new_node
    end
    self
  end
  alias prepend unshift

  # リストの末尾に要素を追加します。
  #
  # data - リストに追加するデータ。
  #
  # Returns nothing.
  def push(data)
    if @head.nil?
      @head = ListNode.new(data)
      @head.next = @head # 最初の要素が最後の要素を指す
    else
      current = @head
      current = current.next while current.next != @head
      current.next = ListNode.new(data)
      current.next.next = @head # 最後の要素が最初の要素を指す
    end
    self
  end

  # リストの先頭から要素を取り出します。
  #
  # _n - 取り出す要素の数。
  #      この引数は無視されます。
  #
  # Returns 取り出された要素のデータ、リストが空の場合はnilを返します。
  def shift(_n = nil)
    return nil if @head.nil?

    if @head.next == @head
      data = @head.data
      @head = nil
      return data
    end
    data = @head.data
    head = @head
    @head = @head.next
    last_node = @head
    last_node = last_node.next while last_node.next != head
    last_node.next = @head
    data
  end

  # リストの末尾から要素を取り出します。
  #
  # _n - 取り出す要素の数。
  #      この引数は無視されます。
  #
  # Returns 取り出された要素のデータ、リストが空の場合はnilを返します。
  def pop(_n = nil)
    return nil if @head.nil?

    if @head.next == @head
      data = @head.data
      @head = nil
      return data
    end

    last_node = @head.next
    prev_node = @head
    while last_node.next != @head
      prev_node = last_node
      last_node = last_node.next
    end
    data = last_node.data
    prev_node.next = @head
    data
  end

  # リストをトラバースして各ノードに対してブロックを適用します。
  #
  # Returns nothing.
  def each
    return to_enum unless block_given?

    return unless @head

    current = @head
    loop do
      yield(current.data) if block_given?
      current = current.next
      break if current == @head
    end
  end
end

def SinglyCircularLinkedList(args, &block) = SinglyCircularLinkedList.new(args, &block)
    
require 'minitest/spec'

describe SinglyCircularLinkedList do
  let(:list) { SinglyCircularLinkedList.new }

  describe '#initialize' do
    it 'initializes an empty list if no arguments are provided' do
      list = SinglyCircularLinkedList.new
      expect(list.to_a).must_equal []
    end

    it 'initializes with an array' do
      list = SinglyCircularLinkedList.new([1, 2, 3])
      expect(list.to_a).must_equal [1, 2, 3]
    end

    it 'initializes with a block' do
      list = SinglyCircularLinkedList.new(3) { |i| i + 1 }
      expect(list.to_a).must_equal [1, 2, 3]
    end

    it 'raises ArgumentError if negative size is provided' do
      expect { SinglyCircularLinkedList.new(-1) }.must_raise ArgumentError
    end

    it 'raises ArgumentError if unexpected arguments are provided' do
      expect { SinglyCircularLinkedList.new('unexpected') }.must_raise ArgumentError
    end
  end

  describe '#unshift' do
    it 'adds an element to the beginning of the list' do
      list.unshift(1)
      list.unshift(2)
      expect(list.to_a).must_equal [2, 1]
    end
  end

  describe '#prepend' do
    it 'is an alias for #unshift' do
      list.prepend(1)
      list.prepend(2)
      expect(list.to_a).must_equal [2, 1]
    end
  end

  describe '#push' do
    it 'adds an element to the end of the list' do
      list.push(1).push(2)
      expect(list.to_a).must_equal [1, 2]
    end
  end

  describe '#shift' do
    it 'removes and returns the first element of the list' do
      list.push(1).push(2)
      expect(list.shift).must_equal 1
      expect(list.to_a).must_equal [2]
    end

    it 'returns nil if the list is empty' do
      expect(list.shift).must_be_nil
    end
  end

  describe '#pop' do
    it 'removes and returns the last element of the list' do
      list.push(1).push(2)
      expect(list.pop).must_equal 2
      expect(list.to_a).must_equal [1]
    end

    it 'returns nil if the list is empty' do
      expect(list.pop).must_be_nil
    end
  end

  describe '#each' do
    it 'iterates over each element of the list' do
      list.push(1).push(2)
      result = []
      list.each { |data| result << data }
      expect(result).must_equal [1, 2]
    end

    it 'returns an enumerator if no block is given' do
      list.push(1).push(2)
      enum = list.each
      expect(enum.each_with_index.to_a).must_equal [[1, 0], [2, 1]]
    end

    it 'does nothing for an empty list' do
      result = []
      list.each { |data| result << data }
      expect(result).must_equal []
    end
  end
end

Minitest.run if $PROGRAM_NAME == __FILE__

双方向循環リスト

[編集]

双方向循環リスト（Doubly Circular Linked List）は、双方向連結リストの一種であり、各ノードが前後のノードへの参照を持ち、最後のノードが最初のノード、最初のノードが最後のノードを指すように構成されたデータ構造です。つまり、各ノードが前のノードと次のノードの両方への参照を持ち、最後のノードの次のノードが最初のノード、最初のノードの前のノードが最後のノードを指します。

双方向循環リストは、通常の双方向連結リストと循環リストの特徴を組み合わせたもので、以下のような特徴があります。

  1. 双方向性: 各ノードが前のノードと次のノードの両方への参照を持つため、前方向や後方向の走査が容易です。これにより、双方向性の操作が可能になります。
  2. ループ性: 最後のノードが最初のノード、最初のノードが最後のノードを指すため、リストがループしています。これにより、循環的な操作やデータ構造の表現が可能になります。
  3. 先頭と末尾へのアクセスの効率性: 最初のノードと最後のノードへのアクセスが容易であり、それぞれのノードが直接的に参照されるため、アクセス時間が短縮されます。
  4. 無限ループの可能性: 双方向循環リストも無限にループする可能性があります。適切な終了条件を設定しない場合、ループ内での操作が無限に続くことがあります。

双方向循環リストは、双方向連結リストの利点と循環リストの利点を組み合わせ、さまざまなアプリケーションやアルゴリズムに使用されます。例えば、環状バッファやキャッシュの実装、ダブリンゲームのボード表現などで利用されることがあります。

Ruby

[編集]

双方向循環リストは単方向循環リストを継承して実装しました。

dcll.rb
require_relative "scll.rb"

class DoublyCircularLinkedList < SinglyCircularLinkedList
  # ListNode は双方向循環リスト内のノードを表します。
  ListNode = Struct.new(:data, :prev, :next)

  # リストの先頭に要素を追加します。
  #
  # data - リストに追加するデータ。
  #
  # Returns self.
  def unshift(data)
    if @head.nil?
      @head = ListNode.new(data)
      @head.prev = @head
      @head.next = @head
    else
      new_node = ListNode.new(data)
      last_node = @head.prev

      last_node.next = new_node
      new_node.prev = last_node
      new_node.next = @head
      @head.prev = new_node
      @head = new_node
    end
    self
  end
  alias prepend unshift

  # リストの末尾に要素を追加します。
  #
  # data - リストに追加するデータ。
  #
  # Returns nothing.
  def push(data)
    if @head.nil?
      @head = ListNode.new(data)
      @head.prev = @head
      @head.next = @head
    else
      new_node = ListNode.new(data)
      last_node = @head.prev

      last_node.next = new_node
      new_node.prev = last_node
      new_node.next = @head
      @head.prev = new_node
    end
    self
  end
  alias append push

  # リストの先頭から要素を取り出します。
  #
  # _n - 取り出す要素の数。
  #      この引数は無視されます。
  #
  # Returns 取り出された要素のデータ、リストが空の場合はnilを返します。
  def shift(_n = nil)
    return nil if @head.nil?
    if @head.next == @head
      data = @head.data
      @head = nil
      return data
    end
    data = @head.data
    @head.prev.next = @head.next
    @head.next.prev = @head.prev
    @head = @head.next
    data
  end

  # リストの末尾から要素を取り出します。
  #
  # _n - 取り出す要素の数。
  #      この引数は無視されます。
  #
  # Returns 取り出された要素のデータ、リストが空の場合はnilを返します。
  def pop(_n = nil)
    return nil if @head.nil?
    if @head.next == @head
      data = @head.data
      @head = nil
      return data
    end
    @head = @head.prev
    data = @head.data
    @head.prev.next = @head.next
    @head.next.prev = @head.prev
    @head = @head.next
    data
  end
end

def DoublyCircularLinkedList(args, &block) = DoublyCircularLinkedList.new(args, &block)
    
require 'minitest/spec'

describe DoublyCircularLinkedList do
  let(:list) { DoublyCircularLinkedList.new }

  describe '#initialize' do
    it 'initializes an empty list' do
      expect(list.to_s).must_equal '()'
    end

    it 'initializes with an array' do
      list = DoublyCircularLinkedList.new([1, 2, 3])
      expect(list.to_s).must_equal '(1 2 3)'
    end

    it 'initializes with an integer' do
      list = DoublyCircularLinkedList.new(3)
      expect(list.to_s).must_equal '(0 1 2)'
    end

    it 'initializes with an array and block' do
      list = DoublyCircularLinkedList.new([1, 2, 3]) { |i| i * 2 }
      expect(list.to_s).must_equal '(2 4 6)'
    end

    it 'initializes with an integer and block' do
      list = DoublyCircularLinkedList.new(3) { |i| i * 2 }
      expect(list.to_s).must_equal '(0 2 4)'
    end
  end

  describe '#push' do
    it 'adds an element to the end of the list' do
      list.push(1)
      expect(list.to_s).must_equal '(1)'
      list.push(2)
      expect(list.to_s).must_equal '(1 2)'
    end
  end

  describe '#pop' do
    it 'removes and returns the last element of the list' do
      list.push(1).push(2)
      expect(list.pop).must_equal 2
      expect(list.to_s).must_equal '(1)'
    end

    it 'returns nil if the list is empty' do
      expect(list.pop).must_be_nil
    end
  end

  describe '#unshift' do
    it 'adds an element to the beginning of the list' do
      list.unshift(1)
      expect(list.to_s).must_equal '(1)'
      list.unshift(2)
      expect(list.to_s).must_equal '(2 1)'
    end
  end

  describe '#shift' do
    it 'removes and returns the first element of the list' do
      list.push(1).push(2)
      expect(list.shift).must_equal 1
      expect(list.to_s).must_equal '(2)'
    end

    it 'returns nil if the list is empty' do
      expect(list.shift).must_be_nil
    end
  end

  describe '#each' do
    it 'iterates over each element of the list' do
      list.push(1).push(2)
      result = []
      list.each { |data| result << data }
      expect(result).must_equal [1, 2]
    end

    it 'returns an enumerator if no block is given' do
      list.push(1).push(2)
      enum = list.each
      expect(enum.each_with_index.to_a).must_equal [[1, 0], [2, 1]]
    end

    it 'does nothing for an empty list' do
      result = []
      list.each { |data| result << data }
      expect(result).must_equal []
    end
  end
end
Minitest.run if $PROGRAM_NAME == __FILE__

リスト構造の操作

[編集]

リスト構造では、主に次の操作が行われます：

  • 要素の挿入: リストの任意の位置に新しい要素を挿入します。
  • 要素の削除: リストから要素を削除します。
  • 要素の検索: 特定の要素を探します。
  • リストの結合: 2つのリストを結合して1つのリストにします。

これらの操作は、ポインタを再配置することで実現されます。

様々なプログラミング言語におけるリスト構造とその操作

[編集]

様々なプログラミング言語でリスト構造がサポートされています。例えば、C言語ではポインタを使用して自前でリストを実装することが一般的です。JavaやC#などの言語では、リストを抽象化したデータ構造が提供されており、要素の追加や削除が容易に行えます。

反復処理

[編集]

リスト内の要素を一つずつ処理するために反復処理が利用されます。これは、各要素を順番に取り出して特定の処理を施すために使用されます。例えば、リスト内のすべての要素を合計する場合などに利用されます。

ユースケース

[編集]

リスト構造は、データの集合を管理する必要がある場面で広く使用されます。例えば、データベースから取得した複数の行を処理する際や、ファイル内のテキスト行を読み込む際に利用されます。また、キューやスタックなどのデータ構造を実装するための基盤としても使用されます。

ベストプラクティス

[編集]

要素の追加や削除が頻繁に行われる場合は、リスト構造を使用します。 検索やランダムアクセスが頻繁に行われる場合は、他のデータ構造（例えば、配列）を検討します。

"https://ja.wikibooks.org/w/index.php?title=リスト構造&oldid=244696" より作成