1.定義接口
public interface SeqList<E>{
//默認(rèn)尾插
void add(E element);
// 在線性表中插入新元素，插入后的元素下標(biāo)為index
void add(int index,E element);
//頭插
public void addFirst(E val);
// 刪除當(dāng)前線性表中索引為index的元素，返回刪除的元素值
E removeByIndex(int index);
// 刪除當(dāng)前線性表中第一個值為element的元素
void removeByValue(E element);
// 刪除當(dāng)前線性表中所有值為element的元素
void removeAllValue(E element);
// 將當(dāng)前線性表中index位置的元素替換為element，返回替換前的元素值
E set(int index,E element);
//返回索引位index的元素
E get(int index);
//查詢是否包含element元素
boolean contains(E element);
}
2.無頭單鏈表實現(xiàn)接口
鏈表類和節(jié)點類的定義：
public class SingleLinkedList<E> implements SeqList<E>{
private Node head ;//第一節(jié)車廂的地址
private int size;//車廂節(jié)點的個數(shù)，保存的元素個數(shù)
//定義一個車廂類，車廂作為火車的私有內(nèi)部類，對外部完全隱藏
private class Node{
E val;//保存的元素
Node next;//下一節(jié)車廂的地址
//構(gòu)造方法
Node(E val){
this.val=val;
}
}
}
2.1 頭插addFirst
public void addFirst(E val){
Node node=new Node(val);
node.next=head;
node=head;
size++;
}
圖解：
2.2 尾插add
從中間位置插入：
@Override
public void add(int index, E element) {
if(index<0||index>size){
throw new IllegalArgumentException("add index ILLegal");
}
//判斷沒有前驅(qū)的情況
if(index==0){
addFirst(element);
return;
}
//中間位置插入
Node prey=head;
for(int i=0;i<index-1;i++){
prey=prey.next;
}
Node node=new Node(element);
node.next=prey.next;
prey.next=node;
size++;
}
圖解：假定index=2
尾插：
@Override
public void add(E element) {
add(size,element);
}
2.3 刪除元素remove
刪除當(dāng)前線性表中索引為index的元素，返回刪除的元素值：
@Override
public E removeByIndex(int index) {
if(rangeCheck(index)){
throw new IllegalArgumentException("remove index Illegal");
}
//頭節(jié)點的刪除
if(index==0){
Node node=head;
head=head.next;
node.next=null;
size--;
return node.val;
}
//中間位置刪除
Node prey=head;
for(int i=0;i<index-1;i++){
prey=prey.next;
}
Node node=prey.next;
prey.next=node.next;
node.next=null;
size--;
return node.val;
}
圖解：
刪除當(dāng)前線性表中第一個值為element的元素：
@Override
public void removeByValue(E element) {
//1.base case
if(head==null){
return;
}
//2.判斷頭節(jié)點恰好是待刪除的節(jié)點
if(head.val.equals(element)){
head=head.next;
size--;
return;
}
//3.此時頭節(jié)點不為空其一定不是待刪除的節(jié)點
Node prey=head;
while(prey.next!=null){
if(prey.next.equals(element)){
prey.next=prey.next.next;
size--;
return;
}
prey=prey.next;
}
//4.當(dāng)前鏈表不存在值為element的元素
System.out.println("當(dāng)前鏈表不存在值為"+element+"的元素");
}
刪除當(dāng)前線性表中所有值為element的元素：
@Override
public void removeAllValue(E element) {
//1.base case
if(head==null){
return;
}
//2.若頭節(jié)點就是待刪除的節(jié)點且出現(xiàn)連續(xù)的待刪除的節(jié)點
while(head!=null && head.val.equals(element)){
head=head.next;
size--;
}
//整個鏈表已經(jīng)刪完了
if(head==null){
return;
}
//3.頭節(jié)點一定不是待刪除的元素且鏈表不為空
Node prey=head;
while(prey.next!=null){
if(prey.next.val.equals(element)){
prey.next=prey.next.next;
size--;
}else{
//只有后繼節(jié)點不是待刪除的節(jié)點才能移動Prey的引用
prey=prey.next;
}
}
}
2.4 修改元素set
將當(dāng)前線性表中index位置的元素替換為element，返回替換前的元素值：
// 將當(dāng)前線性表中index位置的元素替換為element，返回替換前的元素值
@Override
public E set(int index, E element) {
if(!rangeCheck(index)){
throw new IllegalArgumentException("set index illegal");
}
Node x=head;
//遍歷，走到index對應(yīng)的元素
for (int i = 0; i < index; i++) {
x=x.next;
}
E oldVal=x.val;
x.val=element;
return oldVal;
}
//合法性校驗
private boolean rangeCheck(int index){
if(index<0||index>=size){
return false;
}
return true;
}
2.5 獲取元素get
返回索引為index的元素：
@Override
public E get(int index) {
if(!rangeCheck(index)){
throw new IllegalArgumentException("get index illegal");
}
Node x=head;
for(int i=0;i<index;i++){
x=x.next;
}
return x.val;
}
3.帶頭單鏈表實現(xiàn)接口
由于單鏈表中都需要額外處理頭結(jié)點的情況，引入一個虛擬頭結(jié)點，這個節(jié)點不存在具體的值，就作為鏈表的頭來使用，使每個有值的節(jié)點都有一個前驅(qū)。（所有操作都統(tǒng)一了，無論是插入還是刪除，都可以看作是中間位置的插入和刪除）
鏈表類和節(jié)點類的定義：
public class SingleLinkedListWithHead <E> implements SeqList<E>{
//當(dāng)前鏈表一定存在火車頭且不存儲任何元素
private Node dummyHead=new Node(null);
//具體的元素個數(shù)
private int size;
private class Node{
E val;
Node next;
Node(E val){
this.val=val;
}
}
}
3.1 頭插addFirst
public void addFirst(E val){
Node node=new Node(val);
node.next=dummyHead.next;
dummyHead.next=node;
size++;
}
圖解：文章來源：http://www.zghlxwxcb.cn/news/detail-628706.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-628706.html
3.2 尾插add
@Override
public void add(E element) {
add(size,element);
return;
}
@Override
public void add(int index, E element) {
if(index<0||index>size){
throw new IllegalArgumentException("Remove index illegal");
}
Node prey=dummyHead;
for(int i=0;i<index;i++){
prey=prey.next;
}
Node node=new Node(element);
node.next=prey.next;
prey.next=node;
size++;
}
3.3 刪除元素remove
@Override
public void removeAllValue(E element) {
//prey一定指向不是待刪除的節(jié)點
Node prev=dummyHead;
while(prev.next!=null){
if(prev.next.val==element){
prev.next=prev.next.next;
size--;
}else{
prev=prev.next;
}
}
}
3.4 判斷是否包含元素element
@Override
public boolean contains(E element) {
while(dummyHead.next!=null){
if(dummyHead.next.val.equals(element)){
return true;
}
dummyHead.next=dummyHead.next.next;
}
return false;
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】實現(xiàn)單鏈表的增刪查的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
