5-3-3單向鏈結串列刪除節點
在單向鏈結型態的資料結構中，如果要在串列中刪除一個節點，如同一列火車拿掉原有的車廂，依據所刪除節點的位置有三種不同的情形：
演算法如下：
top=head;
head=head.next;
演算法如下：
ptr.next=tail;
ptr.next=null;
演算法如下：
Y=ptr.next;
ptr.next=Y.next;
class employee{
constructor() {
this.num=0;
this.salary=0;
this.name=”;
this.next=null;
}
}
JS del_node.js
class employee{
constructor(){
this.num=0;
this.salary=0;
this.name='';
this.next=null;
}
}
var del_ptr=(head,ptr)=>{ //刪除節點副程式
top=head;
if (ptr.num==head.num) { //[情形1]：刪除點在串列首
head=head.next;
process.stdout.write('已刪除第' +ptr.num+' 號員工 姓名：'+ptr.
name+' 薪資：'+ptr.salary);
}
else {
while (top.next!=ptr) //找到刪除點的前一個位置
top=top.next;
if(ptr.next==null) { //刪除在串列尾的節點
top.next=null;
process.stdout.write('已刪除第'+ptr.num+' 號員工 姓名：'+ptr.
name+' 薪資：'+ptr.salary+'\n');
}
else{
top.next=ptr.next;
process.stdout.write('已刪除第 '+ptr.num+' 號員工 姓名：'+ptr.
name+' 薪資：' +ptr.salary+'\n');
}
}
return head;
}
findword=0;
namedata=['Allen','Scott','Mary','John','Mark','Ricky',
'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299],
[1012,42660],[1014,25676],[1018,44145],[1043,52182],
[1031,32769],[1037,21100],[1041,32196],[1046,25776]];
process.stdout.write('員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n');
process.stdout.write('--------------------------------------------------\n');
for(i=0; i<3; i++) {
for (j=0; j<4; j++)
process.stdout.write(data[j*3+i][0]+ '\t'+data[j*3+i][1]+'\t');
console.log();
}
head=new employee(); //建立串列首
if(!head) {
console.log('Error!! 記憶體配置失敗！！');
return;
}
head.num=data[0][0];
head.name=namedata[0];
head.salary=data[0][1];
head.next=null;
ptr=head;
for (i=1; i<12; i++) { //建立串列
newnode=new employee();
newnode.next=null;
newnode.num=data[i][0];
newnode.name=namedata[i];
newnode.salary=data[i][1];
newnode.next=null;
ptr.next=newnode;
ptr=ptr.next;
}
const prompt = require('prompt-sync')();
while(true) {
const findword = parseInt(prompt('請輸入要刪除的員工編號，要結束刪除過程，請輸入-1：'));
if (findword==-1) //迴圈中斷條件
break;
else {
ptr=head;
find=0;
while (ptr!=null) {
if (ptr.num==findword){
ptr=del_ptr(head,ptr);
find=find+1;
head=ptr;
}
ptr=ptr.next;
}
if (find==0)
process.stdout.write('//////////沒有找到///////////\n');
}
}
ptr=head;
process.stdout.write('\t座號\t 姓名\t成績\n'); //列印剩餘串列資料
process.stdout.write('\t======================\n');
while (ptr!=null) {
process.stdout.write('\t['+ptr.num+' ]\t[ '+ptr.name+' ]\t[ '
+ptr.salary+']\n');
ptr=ptr.next;
}
5-3-4單向鏈結串列的反轉
看完了節點的刪除及插入後，各位可以發現在這種具有方向性的鏈結串列結構中增刪節點是相當容易的一件事。而要從頭到尾印整個串列似乎也不難，不過如果要反轉過來列印就真的需要某些技巧了。我們知道在鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將串列反轉，則必須使用三個指標變數。請看下圖說明：
演算法如下：
class employee{
constructor() {
this.num=0;
this.salary=0;
this.name='';
this.next=null;
}
}
var invert=(x)=> { //x為串列的開始指標
p=x; //將p指向串列的開頭
q=null; //q是p的前一個節點
while (p!=null) {
r=q; //將r接到q之後
q=p; //將q接到p之後
p=p.next //p移到下一個節點
q.next=r; //q連結到之前的節點
}
return q;
}
JS rev_node.js
class employee {
constructor() {
this.num=0;
this.salary=0;
this.name='';
this.next=null;
}
}
findword=0;
namedata=['Allen','Scott','Marry','John','Mark','Ricky',
'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299],
[1012,42660],[1014,25676],[1018,44145],[1043,52182],
[1031,32769],[1037,21100],[1041,32196],[1046,25776]];
head = new employee();//建立串列首
if(!head) {
console.log('Error!! 記憶體配置失敗！！');
return;
}
head.num =data[0][0];
head.name=namedata[0];
head.salary=data[0][1];
head.next=null;
ptr=head;
for(i=1; i<12; i++){ //建立串列
newnode=new employee();
newnode.next=null;
newnode.num=data[i][0];
newnode.name=namedata[i];
newnode.salary=data[i][1];
newnode.next=null;
ptr.next=newnode;
ptr=ptr.next;
}
ptr=head;
i=0;
process.stdout.write('原始員工串列節點資料：\n');
while (ptr !=null) { //列印串列資料
process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
+ptr.salary+'] -> ');
i=i+1;
if (i>=3) { //三個元素為一列
console.log();
i=0;
}
ptr=ptr.next;
}
ptr=head;
before=null;
process.stdout.write('\n反轉後串列節點資料：\n');
while (ptr!=null) { //串列反轉，利用三指標
last=before;
before=ptr;
ptr=ptr.next;
before.next=last;
}
ptr=before;
while (ptr!=null) {
process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
+ptr.salary+'] ->');
i=i+1;
if (i>=3) { //三個元素為一列
console.log();
i=0;
}
ptr=ptr.next;
}
array_pop() 刪除陣列最後一個元素。
array_push() 將一個或多個元素加入末端。
array_reverse() 以相反的順序返回陣列。
array_shift() 刪除首個元素。
array_slice() 刪除指定位置的元素，返回陣列。