Listen-OperationenInformatik 2 - Übung

Klemens Schwarz

headlist

Node NodeNode

Anlegen einer Liste

1. Klasse Node implementieren- beliebige Datenkomponenten (?: int, Number, Student, …)- Zeiger auf das nächste Node-Element (next)- Konstruktor implementieren

2. Knoten aneinanderhängenvar n1:Node = new Node(1); var n2:Node = new Node(2, n1);

3. Ersten Knoten (head) merken

?

?

next

Node

Node

n1

Node

n2

head

Knoten vorne einfügen

head

public function prepend(value:Entry):List{

var node:EntryNode = new EntryNode(value, this.head); this.head = node; return this;

}

node

Knoten hinten anhängen

head

public function append(int value):List{ var newNode:Node = new Node(value, null); var node:Node = this.head; var prev:Node = null; while(node != null) {

prev = node; node = node.next; } prev.next = newNode; return this;}

node

newNodeprev

if (this.head == null) this.head = newNode;else {

Länge der Liste ermitteln

public function length():int {

var n:Node = this.head; var count:int = 0; while (n != null) {

count++; n = n.next;

}return count;

}

Ein bestimmtes Element wählen

public function nodeAt(index:int):Node {

var n:Node = this.head; var count:int = 0; while (n != null && count != index){

count++; n = n.next;

}return n;

}

public function search(value:int):Node {

var n:Node = this.head; while (n != null){

if (n.value == value)return n;

n = n.next; }return null;

}

9 7 4

headn

index = 0 index = 1 index = 2

nodeAt(1); oder search(7);

Ein bestimmtes Element ändern

public function setNodeAt(index:int, value:int):void {

var n:Node = this.head; var count:int = 0; while (n != null){

if (count == index) {

n.value = value;return;

}count++; n = n.next;

}}

9 7 4

headn

index = 0 index = 1 index = 2

8

setNodeAt(1, 8);

Ein Element löschen

public function deleteAt(index:int):List {var n:Node = this.head; var prev:Node = null; var count:int = 0; while (n != null){

if (count == index) {if (prev == null)

this.head = n.next;else

prev.next = n.next;return this;

}count++;prev = n; n = n.next;

}return this;

}

9 7 4

headn

index = 0 index = 1 index = 2

deleteAt(1);

index = 1

prev

Sortiert einfügen

public function insertSorted(int value):List{

var prev:Node = null; // previous nodevar node:Node = this.head; // current nodewhile (node != null && node.value < value){

prev = node;node = node.next;

}var n:Node = new Node(value, node);if (prev == null)

this.head = n;else

prev.next = n;return this;

}

1 2 4

headnode insertSorted(3)prev

3n

Gesamte Liste kopieren

public static function clone(List l):List { var result:List = new List(); var n:Node = l.head; while (n != null) { result.append(n.value); n = n.next; } return result; }

head

head

n

Liste umdrehen

public function reverse():void{ var result:List = new List(); var n:Node = this.head; while (n != null) {

result.prepend(n.value); n = n.next;

} head = result.head; }

head

head

n