Goベースの双方向チェーンテーブルの実践

43211 ワード

Goベースの双方向チェーンテーブルの実践
前言
一方向チェーンテーブル、双方向チェーンテーブルについて、次のドキュメントに説明します.チェーンテーブルリファレンスアドレスについて詳しく説明します.
説明
今回は双方向チェーンテーブルで実践
構成要素
  • Element:要素値
  • Prev(*Entry):prevノード
  • Next(*Entry):nextノード
  • length

  • リストメソッドリスト
  • Length():チェーンテーブル長
  • Add(int,interface{}):指定された場所に要素を追加
  • AddFirst(interface{}):ヘッダ
  • に要素を追加
  • Clear():チェーンテーブル
  • をクリア
  • Contains(interface{}):チェーンテーブルに指定された要素が含まれているかどうかを確認する
  • Get(int):指定位置要素
  • を取得する.
  • GetFirst():ヘッダ要素
  • を取得
  • GetLast():末尾要素
  • を取得
  • Pull():ヘッダ要素
  • を除去
  • IndexOf(interface{}):エレメントが存在するindex
  • を検索
  • Pop():末尾要素
  • を除去
  • Push():追加要素
  • Set(int,interface{}):指定された場所の要素内容を変更する
  • Iterator(func(int,*Entry):チェーンテーブルは
  • を遍歴する
  • MoveTo(int,*Entry):要素を指定位置
  • に移動
  • MoveFront(*Entry):要素を頭部
  • に移動
  • MoveBack(*Entry):エレメントを末尾
  • に移動
  • AsList():チェーンテーブルを取得してslice
  • に戻る
    Entryメソッドリスト
  • HasNext():nextノード
  • があるか否かを判定する.
  • Next():nextノード
  • を取得する.
  • Value():ノード要素のコンテンツを取得する
  • 大まかな考え方.
  • ノード制御(prev,next)
  • 再帰
  • 不足
  • 今回の実践でMoveTo実現は,まず現在のノードをチェーンテーブルから除去してからAdd操作を行うことであり,これによりチェーンテーブル自体の優位性が失われ(修正効率が高い),ノード指向を変えることで制御しようとしたが,時間の関係で完了しなかった.より良い方法を提案した仲間がいたら,下にメッセージを残してください,ありがとうございます!
  • コード#コード#
    package list
    
    import (
    	"errors"
    )
    
    type (
    	Entry struct {
    		prev    *Entry
    		next    *Entry
    		element interface{}
    	}
    	LinkedList struct {
    		element *Entry
    		length  int
    	}
    )
    
    var (
    	ErrIndexOutOfBound = errors.New("the location out of index range")
    )
    
    func NewLinkedList() *LinkedList {
    	return &LinkedList{
    		element: nil,
    	}
    }
    
    func (ll *LinkedList) Length() int {
    	return ll.length
    }
    
    func (ll *LinkedList) Add(location int, v ...interface{}) error {
    	length := ll.length
    	if location < 0 || location > length {
    		return ErrIndexOutOfBound
    	}
    	elements := ll.newElement(v...)
    	prev, next, err := ll.getNodeAtInsertLocation(location)
    	if err != nil {
    		return err
    	}
    	first := elements[0]
    	if length == 0 {
    		ll.element = first
    	}
    	last := elements[len(elements)-1]
    	first.prev = prev
    	last.next = next
    	if next != nil {
    		next.prev = last
    	}
    	if prev != nil {
    		prev.next = first
    	}
    	if location == 0 {
    		ll.element = last
    	}
    	ll.length += len(elements)
    	return nil
    }
    
    func (ll *LinkedList) AddFirst(v interface{}) error {
    	return ll.Add(0, v)
    }
    
    func (ll *LinkedList) Clear() {
    	ll.element = nil
    	ll.length = 0
    }
    
    func (ll *LinkedList) Contains(v interface{}) bool {
    	var contain = false
    	ll.Iterator(func(index int, entry *Entry) bool {
    		if entry.element == v {
    			contain = true
    			return true
    		}
    		return false
    	})
    	return contain
    }
    
    func (ll *LinkedList) Get(location int) (*Entry) {
    	if location < 0 || location >= ll.length {
    		return nil
    	}
    	var result *Entry
    	ll.Iterator(func(index int, entry *Entry) bool {
    		if index == location {
    			result = entry
    			return true
    		}
    		return false
    	})
    	return result
    }
    
    func (ll *LinkedList) GetFirst() (*Entry) {
    	return ll.Get(0)
    }
    
    func (ll *LinkedList) GetLast() (*Entry) {
    	return ll.Get(ll.Length() - 1)
    }
    
    func (ll *LinkedList) Pull() error {
    	return ll.Remove(0)
    }
    
    func (ll *LinkedList) IndexOf(v interface{}) int {
    	var result int
    	ll.Iterator(func(index int, entry *Entry) bool {
    		if entry.element == v {
    			result = index
    			return true
    		}
    		return false
    	})
    	return result
    }
    
    func (ll *LinkedList) Pop() error {
    	return ll.Remove(ll.Length() - 1)
    }
    
    func (ll *LinkedList) Push(v ...interface{}) error {
    	if ll.Length() == 0 {
    		return ll.Add(0, v...)
    	} else {
    		return ll.Add(ll.length, v...)
    	}
    }
    
    func (ll *LinkedList) Remove(location int) error {
    	if location < 0 || location >= ll.length {
    		return ErrIndexOutOfBound
    	}
    	if ll.length == 0 {
    		return nil
    	}
    	if ll.length == 1 {
    		ll.Clear()
    	}
    	var resErr error
    	ll.Iterator(func(index int, entry *Entry) bool {
    		if index == location {
    			if location == 0 {
    				el := ll.Get(1)
    				el.prev = nil
    				ll.element = el
    			} else if location == ll.length-1 {
    				el := ll.Get(location - 1)
    				el.next = nil
    			} else {
    				prev := ll.Get(location - 1)
    				next := ll.Get(location + 1)
    				prev.next = next
    				next.prev = prev
    			}
    			ll.length -= 1
    			return true
    		}
    		return false
    	})
    	return resErr
    }
    
    func (ll *LinkedList) Set(locate int, v interface{}) {
    	ll.Iterator(func(index int, entry *Entry) bool {
    		if index == locate {
    			entry.element = v
    			return true
    		}
    		return false
    	})
    }
    
    func (ll *LinkedList) Iterator(iterator func(index int, entry *Entry) bool) {
    	if ll.Length() == 0 {
    		return
    	}
    	var index = 0
    	entry := ll.element
    	for {
    		con := iterator(index, entry)
    		if con {
    			break
    		}
    		if entry.HasNext() {
    			index++
    			entry = entry.Next()
    		} else {
    			break
    		}
    	}
    }
    
    func (ll *LinkedList) MoveTo(location int, entry *Entry) error {
    	if entry == nil {
    		return nil
    	}
    	if location < 0 || location >= ll.length {
    		return ErrIndexOutOfBound
    	}
    	v := entry.element
    	ll.Iterator(func(index int, e *Entry) bool {
    		if entry.element == e.element {
    			ll.Remove(index)
    			return true
    		}
    		return false
    	})
    	ll.Add(location, v)
    	return nil
    }
    
    func (ll *LinkedList) MoveFront(entry *Entry) {
    	ll.MoveTo(0, entry)
    }
    
    func (ll *LinkedList) MoveBack(entry *Entry) {
    	ll.MoveTo(ll.length-1, entry)
    }
    
    func (ll *LinkedList) newElement(v ...interface{}) []*Entry {
    	var elements = make([]*Entry, 0)
    	for index, e := range v {
    		var prev *Entry
    		var element Entry
    		element.element = e
    		if index != 0 {
    			prev = elements[index-1]
    			prev.next = &element
    			element.prev = prev
    		}
    		elements = append(elements, &element)
    	}
    	return elements
    }
    
    // returns prev and current element
    func (ll *LinkedList) getNodeAtInsertLocation(insertLocation int) (*Entry, *Entry, error) {
    	if insertLocation < 0 || insertLocation > ll.Length() {
    		return nil, nil, ErrIndexOutOfBound
    	}
    	if ll.Length() == 0 {
    		return nil, nil, nil
    	}
    	prevIndex := insertLocation - 1
    	nextIndex := insertLocation
    	var prev *Entry
    	var next *Entry
    
    	ll.Iterator(func(index int, entry *Entry) bool {
    		if index == prevIndex {
    			prev = entry
    		}
    		if index == nextIndex {
    			next = entry
    		}
    		return false
    	})
    	return prev, next, nil
    }
    
    func (ll *LinkedList) AsList() []interface{} {
    	result := make([]interface{}, 0)
    	ll.Iterator(func(index int, entry *Entry) bool {
    		result = append(result, entry.element)
    		return false
    	})
    	return result
    }
    
    func (e *Entry) HasNext() bool {
    	return e.next != nil
    }
    
    func (e *Entry) Next() *Entry {
    	return e.next
    }
    
    func (e *Entry) Value() interface{} {
    	return e.element
    }
    
    

    まとめ
    なし
    ソースアドレス
    Github