鏈結串列的介紹可以參考此篇。
//Linked List
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}
//在尾部插入節點
append(data) {
let newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while(current.next){
current = current.next
}
current.next = newNode
}
this.length += 1;
}
//特定位置插入節點
insertAt(index, data) {
// 確認給的位置是否超出實際總數。
if (index < 0 || index >= this.length) {
return null;
}
let newNode = new Node(data);
let current = this.head;
let previous;
let count = 0;
if (index == 0) {
this.head = newNode;
newNode.next = this.head;
} else {
while(count != index){
count ++;
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
this.length += 1;
}
//刪除特定位置節點
removeAt(index) {
if (index < 0 || index >= this.length){
return false;
}
let current = this.head;
let previous;
let count = 0;
if (index === 0) {
this.head = current.next;
} else {
while(count != index){
count ++;
previous = current;
current = current.next;
}
previous.next = current.next
}
this.length -= 1;
}
//刪除特定節點
remove(data) {
let current = this.head;
let previos = null;
while (current != null) {
if (current.data === data) {
if (previos == null) {
this.head = current.next;
} else {
previos.next = current.next;
}
this.length -= 1;
}
previos = current;
current = current.next;
}
}
//回傳第一個出現此資料節點的位置,若空值則回傳-1
indexOf(data) {
let currNode = this.head;
let count = 0;
while (currNode) {
if (currNode.data === data) {
return count;
}
count += 1;
currNode = currNode.next;
}
return -1;
}
//是否為空串列
isEmpty() {
return this.length === 0;
}
//串列長度
size() {
return this.length;
}
//印出串列所有資料
print() {
const temp = [];
let currNode = this.head;
while (currNode) {
temp.push(currNode.data);
currNode = currNode.next;
}
return temp.join(', ');
}
}
let ll = new LinkedList();
console.log(ll.isEmpty());//true
ll.append(10);
ll.append(20);
console.log(ll.isEmpty());//false
console.log(ll.print())//"10, 20"
ll.insertAt(1,60);
console.log(ll.print())//"10, 60, 20"
ll.append(20);
console.log(ll.print())//"10, 60, 20, 20"
ll.removeAt(2)
console.log(ll.print())//"10, 60, 20"
ll.remove(20)
console.log(ll.size())//2
console.log(ll.print())//"10, 60"
#Linked List
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
class LinkedList:
def __init__(self, head=None):
self.head = head
def append(self, data):
if not self.head:
self.head = Node(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)
def insertAt(self, index, data):
if index < 0 or index >= self.size():
return
node = Node(data)
current = self.head
previous = None
count = 0
if index == 0:
self.head = Node(data, node)
else:
while count != index:
count += 1
previous = current
current = current.next
new_node = Node(data, previous.next)
previous.next = new_node
def removeAt(self, index):
if index < 0 or index >= self.size():
return
current = self.head
previous = None
count = 0
if index == 0:
self.head = current.next
else:
while count != index:
count += 1
previous = current
current = current.next
previous.next = current.next
def remove(self, data, all=False):
current = self.head
previous = None
while current:
if current.data == data:
if previous:
previous.next = current.next
current.next = current
else:
self.head = current.next
if not all:
return
else:
previous = current
current = current.next
def indexOf(self, data):
node = self.head
count = 0
while node:
if node.data == data:
return count
count += 1
node = node.next
def isEmpty(self):
return self.head is None
def size(self):
count = 0
node = self.head
while node:
count += 1
node = node.next
return count
def print(self):
if not self.head:
print(self.head)
node = self.head
while node:
end = " -> "
print(node.data, end=end)
node = node.next
ll = LinkedList()
print(ll.isEmpty())#True
ll.append(10)
ll.append(20)
print(ll.isEmpty())#False
print(ll.print())#10 -> 20 -> None
ll.insertAt(1,60)
print(ll.print())#10 -> 60 -> 20 -> None
ll.append(20)
print(ll.print())#10 -> 60 -> 20 -> 20 -> None
ll.remove(20)
print(ll.print())#10 -> 60 -> 20 -> None
ll.removeAt(1)
print(ll.print())#10 -> 20 -> None
ll.remove(20)
print(ll.size())#1
print(ll.print())#10 -> None
鏈結串列的介紹可以參考此篇。
程式碼有一段好像有些錯誤,如下:
insertAt(index, data) {
// 確認給的位置是否超出實際總數。
if (index < 0 || index >= this.length) {
return null;
}
let newNode = new Node(data);
let current = this.head;
let previous;
let count = 0;
if (index == 0) {
this.head = newNode;
// 調整後
newNode.next = current;
} else {
while(count != index){
count ++;
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
this.length += 1;
}