### 链表的结点
- 数据成员
- 指针成员
### 链表的类型
- 线性单向链表
- 线性双向链表
### 链表的结构
- 头结点
- 头指针
- 开始节点
- 终端节点
### LinkNode<E>
class LinkNode<E>
{
E data;
LinkNode<E> next;
public LinkNode() {
next=null;
}
public LinkNode(E d)
{
data=d;
next=null;
}
}
### LinkListClass<E>
public class LinkListClass<E>
{
LinkNode<E> head;
public LinkListClass()
{
head=new LinkNode<E>();
head.next=null;
}
}
### Insert(int i, E e)
public void Insert(int i, E e)
{
if (i<0 || i>size())
throw new IllegalArgumentException
("插入:位置i不在有效范围内");
LinkNode<E> s=new LinkNode<E>(e);
LinkNode<E> p=geti(i-1);
s.next=p.next;
p.next=s;
}
### Delete(int i)
public void Delete(int i)
{
if (i<0 || i>size()-1)
throw new IllegalArgumentException
("删除:位置i不在有效范围内");
LinkNode<E> p=geti(i-1);
p.next=p.next.next;
}
### CreateListF(E[] a)
public void CreateListF(E[] a)
{
LinkNode<E> s;
for (int i=0;i<a.length;i++)
{
s=new LinkNode<E>(a[i]);
s.next=head.next;
head.next=s;
}
}
### CreateListR(E[] a)
public void CreateListR(E[] a)
{
LinkNode<E> s,t;
t=head;
for (int i=0;i<a.length;i++)
{
s=new LinkNode<E>(a[i]);
t.next=s;
t=s;
}
t.next=null;
}
### geti(int i)
private LinkNode<E> geti(int i)
{
LinkNode<E> p=head;
int j=-1;
while (j<i)
{
j++;
p=p.next;
}
return p;
}
### Add(E e)
public void Add(E e)
{
LinkNode<E> s=new LinkNode<E>(e);
LinkNode<E> p=head;
while (p.next!=null)
p=p.next;
p.next=s;
}
### size()
public int size()
{
LinkNode<E> p=head;
int cnt=0;
while (p.next!=null)
{
cnt++;
p=p.next;
}
return cnt;
}
### Setsize(int nlen)
public void Setsize(int nlen)
{
int len=size();
if (nlen<0 || nlen>len)
throw new IllegalArgumentException
("设置长度:n不在有效范围内");
if (nlen==len) return;
LinkNode<E> p=geti(nlen-1);
p.next=null;
}
### GetElem(int i)
public E GetElem(int i)
{
int len=size();
if (i<0 || i>len-1)
throw new IllegalArgumentException
("查找:位置i不在有效范围内");
LinkNode<E> p=geti(i);
return (E)p.data;
}
### SetElem(int i,E e)
public void SetElem(int i,E e)
{
if (i<0 || i>size()-1)
throw new IllegalArgumentException
("设置:位置i不在有效范围内");
LinkNode<E> p=geti(i);
p.data=e;
}
### GetNo(E e)
public int GetNo(E e)
{
int j=0;
LinkNode<E> p=head.next;
while (p!=null && !p.data.equals(e))
{
j++;
p=p.next;
}
if (p==null)
return -1;
else
return j;
}
### swap(int i,int j)
public void swap(int i,int j)
{
LinkNode<E> p=geti(i);
LinkNode<E> q=geti(j);
E tmp=p.data;
p.data=q.data;
q.data=tmp;
}
### toString()
public String toString()
{
String ans="";
LinkNode<E> p=head.next;
while (p!=null)
{
ans+=p.data+" ";
p=p.next;
}
return ans;
}
### 双链表
- 访问后继结点
- 访问前驱结点
### DLinkNode<E>
class DLinkNode<E>
{
E data;
DLinkNode<E> prior;
DLinkNode<E> next;
public DLinkNode()
{ prior=null;
next=null;}
public DLinkNode(E d)
{ data=d;
prior=null;
next=null;}
}
### DLinkListClass<E>
public class DLinkListClass<E>
{
DLinkNode<E> dhead;
public DLinkListClass()
{
dhead=new DLinkNode<E>();
dhead.prior=null;
dhead.next=null;
}
### Insert(int i, E e)
public void Insert(int i, E e)
{
if (i<0 || i>size())
throw new IllegalArgumentException
("插入:位置i不在有效范围内");
DLinkNode<E> s=new DLinkNode<E>(e);
DLinkNode<E> p=dhead=geti(i-1);
s.next=p.next;
if (p.next!=null)
p.next.prior=s;
p.next=s;
s.prior=p;
}
### Delete(int i)
public void Delete(int i)
{
if (i<0 || i>size()-1)
throw new IllegalArgumentException
("删除:位置i不在有效范围内");
DLinkNode<E> p=geti(i);
p.prior.next=p.next;
if (p.next!=null)
p.next.prior=p.prior;
}
### CreateListF(E[] a)
public void CreateListF(E[] a)
{
DLinkNode<E> s;
for (int i=0;i<a.length;i++)
{
s=new DLinkNode<E>(a[i]);
s.next=dhead.next;
if (dhead.next!=null)
dhead.next.prior=s;
dhead.next=s;
s.prior=dhead;
}
}
### CreateListR(E[] a)
public void CreateListR(E[] a)
{
DLinkNode<E> s,t;
t=dhead;
for (int i=0;i<a.length;i++)
{ s=new DLinkNode<E>(a[i]);
t.next=s;
s.prior=t; t=s;
}
t.next=null;
}
### geti(int i)
private DLinkNode<E> geti(int i)
{
DLinkNode<E> p=dhead;
int j=-1;
while (j<i)
{
j++;
p=p.next;
}
return p;
}
### Add(E e)
public void Add(E e)
{
DLinkNode<E> s=new DLinkNode<E>(e);
DLinkNode<E> p=dhead;
while (p.next!=null)
p=p.next;
p.next=s;
s.prior=p;
}
### size()
public int size()
{
DLinkNode<E> p=dhead;
int cnt=0;
while (p.next!=null)
{
cnt++;
p=p.next;
}
return cnt;
}
### Setsize(int nlen)
public void Setsize(int nlen)
{
int len=size();
if (nlen<0 || nlen>len)
throw new IllegalArgumentException
("设置长度:n不在有效范围内");
if (nlen==len) return;
DLinkNode<E> p=geti(nlen-1);
p.next=null;
}
### GetElem(int i)
public E GetElem(int i)
{
int len=size();
if (i<0 || i>len-1)
throw new IllegalArgumentException
("查找:位置i不在有效范围内");
DLinkNode<E> p=geti(i);
return (E)p.data;
}
### SetElem(int i,E e)
public void SetElem(int i,E e)
{
if (i<0 || i>size()-1)
throw new IllegalArgumentException
("设置:位置i不在有效范围内");
DLinkNode<E> p=geti(i);
p.data=e;
}
### GetNo(E e)
public int GetNo(E e)
{
int j=0;
DLinkNode<E> p=dhead.next;
while (p!=null && !p.data.equals(e))
{
j++;
p=p.next;
}
if (p==null)
return -1;
else
return j;
}
### toString()
{
String ans="";
DLinkNode<E> p=dhead.next;
while (p!=null)
{
ans+=p.data+" ";
p=p.next;
}
return ans;
}
### 循环链表
- 循环单链表
- 循环双链表
### 循环单链表
- head.next == head;
- p.next == head;
### 循环双链表
- dhead.prior == dhead;
- dhead.next == dhead;
## 9.4 顺序表和链表的比较
### 基于空间考虑
- 顺序表存储密度高
- 顺序表需要预先分配空间
### 基于时间考虑
- 顺序表查找的时间复杂度为 $O(1)$
- 链表插入和删除的时间复杂度为 $O(1)$
### 9.3 线性表的链式存储结构
- 数据成员用来存储什么类型的信息?
- 指针成员在单向链表和双向链表中有什么不同?
- 头结点和头指针有什么不同?
- 在双链表中, 如何访问一个节点的后继结点?
- 顺序表和链表在时间和空间复杂度上有什么区别?
----
[ 9.1 线性表的定义](dbds-9-1.html#/overview)
[| 练习 |](dbds-exec.html)
[ 9.5 栈](dbds-9-5.html#/overview)
黑公网安备23010302001726号