Today ：復習數(shù)據(jù)結構鏈表

數(shù)據(jù)結構之鏈表
對比分析：
棧和隊列：申請連續(xù)空間，順序存儲數(shù)據(jù)
鏈表：物理上非連續(xù)、非順序存儲結構，數(shù)據(jù)之間通過指針關聯(lián)
與數(shù)組對比：無需提前設置長度，可以更好的利用計算機內存。
特點總結：
物理空間不連續(xù)
運行過程中可動態(tài)添加
查找元素需順序查找
操作繁瑣復雜

包括：刪除、添加功能。
public class Node {
private int data;
private Node next;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public class Link {
private int size = 0;
private Node first;
private Node last;
public Link(){
}
在鏈表中插入第一個元素時，頭尾元素都是一個元素
private void fillStart(int data){
first = new Node();
first.setData(data);
last = first;
}
在鏈表中查找某個位置的元素
public Node findNode(int index){
Node temp = first;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
鏈表后部插入
public void addLast(int data){
if (size == 0){
fillStart(data);
}else {
Node node = new Node();
node.setData(data);
last.setNext(node);
把最后插入的元素設置為鏈表尾的元素
last = node;
}
size++;
}
鏈表頭部插入
public void addFirst(int data){
if (size == 0){
fillStart(data);
}else {
Node n = new Node();
n.setData(data);
把元素的下一個位置的指針指向頭元素
n.setNext(first);
將剛插入的元素放置到表頭位置
first = n;
}
size++;
}
指定位置“后面”插入元素,index從0開始
public void addIndex(int data, int index){
插入的元素size > index索引部分
if (size > index){
if (size == 0 ){
fillStart(data);
size++;
}else if (index == 0){
addFirst(data);
}else if (index == size - 1){
addLast(data);
}else {
//abcdf
Node temp = findNode(index);
Node n = new Node();
n.setData(data);
n.setNext(temp.getNext());
temp.setNext(n);
size++;
}
}else {
throw new IndexOutOfBoundsException("異常，索引位置超出元素大小");
}
}
清空，只有一個結點
public void clear(){
first =null;
last = null;
size = 0;
}
鏈表頭部刪除
public void removeFirst(){
if (size == 0){
throw new IndexOutOfBoundsException("已無鏈表元素可刪了");
}else if (size == 1){
clear();
}else {
Node temp = first;
first = temp.getNext();
temp = null;
size--;
}
}
鏈表尾部刪除
public void removeLast(){
if (size == 0){
throw new IndexOutOfBoundsException("已無鏈表元素可刪了");
}else if (size == 1){
clear();
}else {
//找到倒數(shù)第二個結點
Node temp = findNode(size - 2);
temp.setNext(null);
size--;
}
}
刪除鏈表中間部分的數(shù)據(jù)
public void removeIndex(int index){
if (size > index){
if (size == 0){
throw new IndexOutOfBoundsException("鏈表無元素可刪除");
}else if (size == 1){
clear();
}else {
if (index == 0){
removeFirst();
}else if (index == size - 1){
removeLast();
}else {
Node temp = findNode(index-1);
temp.setNext(temp.getNext().getNext());
Node temp1 = findNode(index);
temp1 = null;
size--;
}
}
}else {
throw new IndexOutOfBoundsException("異常，索引位置超出元素大小");
}
}
public int size(){
return size;
}
public void printAll(){
Node temp = first;
System.out.print(temp.getData()+" ");
for (int i = 0; i < size - 1; i++) {
temp = temp.getNext();
System.out.print(temp.getData()+" ");
}
}
}